Maximum Difference Between Increasing Elements - Leetcode Solution

Problem Statement:

Given an integer array nums, you need to find the maximum difference between any two adjacent increasing elements in the array.

If there is no such pair, return 0.

Example 1:

Input: nums = [1,2,3,4,5,6,7,8,9] Output: 1 Explanation: The maximum difference is 1 between adjacent elements in the array.

Example 2:

Input: nums = [9,8,7,6,5,4,3,2,1] Output: 0 Explanation: There is no increasing elements in the array.

Approach:

To solve this problem we have to traverse the array and keep track of two variables:

1. Smallest Element so far

2. Maximum Difference so far

For every element we check if it is greater than the smallest element so far, if this condition holds, we calculate the difference of the current element with the smallest element so far and if this difference is greater than the maximum difference so far then we update the maximum difference so far with the new difference. Also, if the current element is smaller than the smallest element so far we update the smallest element so far.

By following the above algorithm we will be able to find the maximum difference between any two adjacent increasing elements in the array.

Let's see the implementation of the above algorithm.

Solution:

class Solution { public: int maximumDifference(vector<int>& nums) {

    int smallest_element_so_far = INT_MAX;
    int max_difference_so_far = 0;
    
    for(int i=0; i<nums.size(); i++){
        if(nums[i] > smallest_element_so_far){
            int current_difference = nums[i] - smallest_element_so_far;
            max_difference_so_far = max(max_difference_so_far, current_difference);
        }
        else{
            smallest_element_so_far = nums[i];
        }
    }
    return max_difference_so_far > 0 ? max_difference_so_far : 0;
}

};

Time Complexity: O(n)

Space Complexity: O(1)

Explanation:

In the above solution we first initialize the smallest_element_so_far variable to INT_MAX and the max_difference_so_far variable to 0.

Then, we iterate through the array and check if the current element is greater than the smallest element so far. If this condition holds true then we calculate the difference between the current element and the smallest element so far and store it in the current_difference variable. After that we check if this current difference is greater than the maximum difference so far, if this condition holds true then we update the max_difference_so_far variable with the new difference.

If the current element is not greater than the smallest element so far then we update the smallest_element_so_far variable.

At last, we return the max_difference_so_far variable if it is greater than 0 otherwise we return 0.

The time complexity of the solution is O(n) as we are traversing the array only once.

The space complexity of the solution is O(1) as we are not using any extra space apart from the given array.

1