DDSA Solutions

2016. Maximum Difference Between Increasing Elements

EasyView on LeetCode
Array
Time: O(n)
Space: O(1)

Problem Overview

Maximum difference where larger element comes after smaller element.

Intuition

Maximum difference where larger element comes after smaller element. Track minimum seen so far, compute diff at each step.

Algorithm

  1. 1min_so_far = nums[0]. max_diff = -1.
  2. 2For each i from 1: if nums[i] > min_so_far: max_diff = max(max_diff, nums[i]-min_so_far). Update min_so_far.

Common Pitfalls

  • •Must have j > i and nums[j] > nums[i]. Track minimum to the left. Return -1 if no valid pair.
2016.cs
C#
// Approach: Track running minimum; for each element compute diff with running min; take max.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaximumDifference(int[] nums)
    {
        // Initialize the minimum value to a very large value
        int minVal = int.MaxValue;
        // Initialize the answer to -1, assuming there is no positive difference found
        int maxDiff = -1;

        // Loop through each number in the input array
        foreach (int num in nums)
        {
            // If the current number is greater than the minimum value found so far
            if (num > minVal)
            {
                // Update the maximum difference with the greater value between the current maximum difference
                // and the difference between the current number and the minimum value found so far
                maxDiff = Math.Max(maxDiff, num - minVal);
            }
            else
            {
                // If the current number is not greater than the minimum value found so far,
                // then update the minimum value to the current number
                minVal = num;
            }
        }

        // Return the maximum difference found, or -1 if no positive difference exists
        return maxDiff;
    }
}
Was this solution helpful?

Related Problems