Maximum Difference Between Two Elements Such that Larger Element Appears After the Smaller Number

Posted in

Maximum Difference Between Two Elements Such that Larger Element Appears After the Smaller Number
vinaykhatri

Vinay Khatri
Last updated on July 21, 2024

    Problem

    Find the maximum difference between two array elements such that the bigger element appears after, the smaller.

    Brute Force approach

    Utilize two loops. Pick items one by one in the outer loop and in the inner loop, compute the difference between the selected element and every other element in the array and compare the difference to the largest difference determined so far.  This takes O(N 2 ) time. Can we do better? Let’s see!

    Efficient approach

    In this technique, instead of taking the difference between the selected element and every other element, we take the difference between the selected element and the smallest element found thus far. So we must keep two things on track:

    1. The greatest difference discovered thus far.
    2. The smallest number of elements viewed so far.

    This approach takes only O(N) time and O(1) space.

    C Programming

    #include<stdio.h>
    int solve(int arr[], int n)
    {
    int ans = arr[1] - arr[0];   //keep track of answer
    int minElement = arr[0];  //keep track of minimum element
    int i;
    for(i = 1; i < n; i++)
    {   
        if (arr[i] - minElement > ans)        //update answer                  
        ans = arr[i] - minElement;
        if (arr[i] < minElement)
            minElement = arr[i];                    
    }
    return ans;
    }
    
    void main(){
        int a[]={1, 2, 3, 4, 7, 3, 5};
        int n = sizeof(a)/sizeof(a[0]);
        printf("%d",solve(a, n));
    }

    Output

    6

    C++ Programming

    #include <bits/stdc++.h>
    using namespace std;
    
    int solve(int arr[], int n)
    {
         // max difference 
         int ans = arr[1] - arr[0];
          
         // minimum element
         int minElement = arr[0];
         for(int i = 1; i < n; i++)
         {    
           if (arr[i] - minElement > ans)                            
           ans = arr[i] - minElement;
            
           if (arr[i] < minElement)
           minElement = arr[i];                    
         }
          
         return ans;
    }
    
    int main(){
        int a[]={1, 2, 3, 4, 7, 3, 5};
        int n = sizeof(a)/sizeof(a[0]);
        cout<<solve(a, n);
    }

    Output

    6

    Python Programming

    def solve(arr, n):
        ans = arr[1] - arr[0]  #keep track of difference
        minElement = arr[0]    #keep track of minimum element
        
        for i in range( 1, n ):
            if (arr[i] - minElement > ans):  #update answer
                ans = arr[i] - minElement
        
            if (arr[i] < minElement):
                minElement = arr[i]
        return ans
    
    l = [1, 2, 3, 4, 7, 3, 5]
    
    n = len(l)
    
    print(solve(l,n))

    Output 6 People are also reading:

    Leave a Comment on this Post

    0 Comments