Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Naive Approach
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Time Complexity Analysis
2.2.2.
Space complexity Analysis
3.
Dynamic Programming Approach
3.1.
Kadane’s Algorithm
3.2.
Implementation in C++
3.2.1.
Time Complexity Analysis
3.2.2.
Space complexity Analysis
4.
Frequently Asked Questions
4.1.
How do you simply find the maximum difference between two elements in an array?
4.2.
How is dynamic programming helpful?
4.3.
What is the asymptotic complexity of finding an array element based on an index?
5.
Conclusion
Last Updated: Mar 27, 2024
Medium

Maximum difference between two elements such that larger element appears after the smaller number

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

Finding the maximum difference between two elements such that the larger element appears after the smaller number from a given array is a medium DSA implementation-based problem that can be solved using the concept of array traversal. Here first, we will discuss the brute force approach and then the optimized method.

Also See, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

We are given an array of integers. Help 'Ninja' to find the maximum difference between two elements where the larger element appears after the smaller element or find a[i] and a[j] such that a[j]-a[i] ( j > i ) is the maximum.

Sample Examples

Example 1

Input

Output

Maximum difference: 8

Explanation

The maximum difference is 8 between 10 and 2.

Example 2

Input

Output 

Maximum difference: 16

Explanation

The maximum difference is 16 between 19 and 3.

Naive Approach

We simply use two nested loops in the basic technique. Taking each element one at a time and comparing it to all the others while keeping track of the largest difference elements where the larger element appears after the smaller element.

Algorithm

  1. Traverse the array from left to right, and run a nested for loop for j=i+1.
  2. Declare a variable maxdifference to store the maximum difference, and keep on comparing a[j] - a[i] for j>i.
  3. Return the maxdifference variable.

Implementation in C++

#include <bits/stdc++.h>
#include <cmath>

using namespace std;

//if the array is in decreasing order function returns -1
int max_diff(int a[], int n)
{
    int maxdifference = a[1] - a[0];
    for (int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++)
        {
            if (a[j] - a[i] > maxdifference)
                maxdifference = a[j] - a[i];
         }
     }
     return maxdifference;
}

int main()
{
    int arr[] = {2, 5, 4, 10, 4, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference : ";
    cout<< max_diff(arr, n);
    return 0;
}


Output

Time Complexity Analysis

The time complexity is O(n^2) because we are using two nested loops.

Space complexity Analysis

Because we don't use auxiliary space, the space complexity is O(1).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Dynamic Programming Approach

We can use a modified version of Kadane's algorithm. The method is quite effective and involves dynamic programming.

Kadane’s Algorithm

  1. From right to left, traverse the array.
  2. Use two variables: maxDifference (final answer) and currSum which stores the first two items' differences.
  3. Compute Prefix Sum.
    1. if (current difference > zero), Add the difference between the following array members.
    2. else: current difference is equal to the current consecutive element’s difference.
  4. Compare the sum of current differences with maxDifference and update accordingly.
  5. Return the maxDifference as the final answer.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

int max_diff(int arr[], int n)
{
    int diff = arr[1]-arr[0];
    int curr_sum = diff;
    int maxDifference = curr_sum;
    
    for(int i=1; i<n-1; i++)
    {
        // Calculate the current diff
        diff = arr[i+1]-arr[i];
        
        // Calculate the current_sum
        if (curr_sum > 0)
            curr_sum = curr_sum + diff;
        else
            curr_sum = diff;
            
        // Update maxdifference, if needed
        maxDifference = max(maxDifference, curr_sum );
    }
    return maxDifference;
}

int main()
{
    int arr[] = {2, 5, 4, 10, 4, 9};
    //size of the array
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Maximum difference : " << max_diff(arr, n);
    return 0;
}


Output

Time Complexity Analysis

The time complexity is O(n), as iterating over a loop of size n results in an O(n) complexity.

Space complexity Analysis

We don't use any auxiliary space, the space complexity is O(1).

Frequently Asked Questions

How do you simply find the maximum difference between two elements in an array?

Make use of two loops. Pick elements one by one in the outer loop, then compute the difference between the picked element and every other element in the array in the inner loop and compare it to the maximum difference determined so far.
 

How is dynamic programming helpful?

Dynamic Programming is a technique that helps to efficiently solve problems that have overlapping subproblems and optimal substructure properties.
 

What is the asymptotic complexity of finding an array element based on an index?

It is constant O(1).

Conclusion

This article extensively discussed the problem of finding the maximum difference between two elements such that the larger element appears after the smaller number. We discussed two approaches to solve the problem and implemented both approaches in C++ and discussed their complexities in both the cases.

We hope this blog has helped you enhance your knowledge regarding finding the maximum difference in an array.  Are you interested in reading/exploring additional articles about this topic? Don't worry; Coding Ninjas has you covered. See Time Complexity and AnalysisBook Allocation ProblemSorting Based ProblemsNumber Theory, and Dynamic Programing to learn.

Refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive Programming, and many more! You can also check Interview Experiences and Interview Preparation Resources if you are interested in cracking the technical interviews at top Product-based companies like Amazon, Microsoft, Uber, etc.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Maximum difference between a group of k-elements and rest of the array
Next article
Given an array arr[], find the maximum j – i such that arr[j] > arr[i]
Live masterclass