algoadvance

Leetcode 2016. Maximum Difference Between Increasing Elements

Problem Statement

Given a 0-indexed integer array nums of size n, you need to find the maximum difference between nums[i] and nums[j] (i.e., nums[j] - nums[i]), such that 0 <= i < j < n and nums[i] < nums[j]. Return the maximum difference. If no such i and j exist, return -1.

Clarifying Questions

  1. Can the array contain negative numbers?
    • Yes, the array can contain negative numbers.
  2. What is the maximum possible size of the array?
    • The size of the array (n) can go up to 10^4.
  3. Should the difference be strictly positive?
    • Yes, we need nums[j] > nums[i].
  4. What if the array has less than two elements?
    • In that case, returning -1 would be appropriate since finding such pairs is not possible.

Strategy

  1. Initialize:
    • A variable min_element to keep track of the minimum element seen so far and set it to nums[0].
    • A variable max_diff to keep the maximum difference found and set it to -1.
  2. Iterate through the array:
    • For each element starting from the second element, check if it is greater than min_element.
      • If true, update max_diff with the maximum of max_diff and (current_element - min_element).
    • Update min_element if the current element is smaller.
  3. Return:
    • After iterating through the array, return max_diff.

Time Complexity

Code

public class Solution {
    public int maximumDifference(int[] nums) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        
        int min_element = nums[0];
        int max_diff = -1;
        
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > min_element) {
                max_diff = Math.max(max_diff, nums[i] - min_element);
            } else {
                min_element = nums[i];
            }
        }
        
        return max_diff;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int result = sol.maximumDifference(new int[]{7, 1, 5, 4});
        System.out.println(result); // Output should be 4 (5 - 1)
    }
}

Explanation

  1. Initialization: We initialize min_element to the first element and max_diff to -1.
  2. Iteration: Start iterating from the second element. If the current element is greater than min_element, update max_diff. Otherwise, update min_element.
  3. Return: Once the loop ends, return max_diff. If no valid i, j pairs were found, max_diff remains -1.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI