Maximum Difference Between Increasing Elements
To solve this problem, we can use a simple onepass algorithm. We maintain a variable min_val
to store the minimum value found so far and max_diff
to store the maximum difference found so far.


Here’s what this code does:
We first initialize
min_val
with the first element of the array andmax_diff
as1
because it’s the smallest possible output value.We then iterate over the array starting from the second element (
nums[1]
).If the current element is greater than
min_val
, we calculate the difference (nums[i]  min_val
) and updatemax_diff
if this difference is greater than the currentmax_diff
.If the current element is not greater than
min_val
, it becomes the newmin_val
.We repeat this process for all elements in the array. At the end,
max_diff
will hold the maximum difference as per the problem statement.
This works because we are essentially looking for the greatest upward ‘jump’ in the array. By maintaining the minimum value seen so far (min_val
), we are always ready to calculate the maximum difference when we see a larger value.
Building Blocks
The building blocks of this solution are:
Array traversal: This solution requires a single pass through the given array, from the second element to the last. This is a common technique used in many problems involving arrays.
Tracking minimum value: As we move through the array, we continually update the minimum value seen so far. This helps us to calculate the maximum difference when we encounter a larger value.
Tracking maximum difference: This involves constantly comparing and updating a stored value (
max_diff
) based on current computations (nums[i]  min_val
), another common technique in a variety of problems.Comparison operations: The solution involves comparing numbers to determine if one is greater than the other (
nums[i] > min_val
) and to find the maximum difference (max_diff = max(max_diff, nums[i]  min_val)
).Conditional logic: Depending on whether the current number is greater than the minimum value seen so far, we choose to either update
max_diff
ormin_val
.Return the result: Finally, the maximum difference found during the traversal is returned as the result.
These building blocks are utilized together to build the solution for the problem.
I see Running Maximum Difference, Running Minimum. Is there others?
Yes, in addition to “Running Minimum” and “Running Maximum Difference”, there are a few more concepts at play here:
Sequential Access: We traverse the list in a sequential manner, one element after another. This is an essential concept for a majority of arraybased problems.
Greedy Approach: The idea of always taking the best option available at the moment (updating
max_diff
whenever we see a larger difference, or updatingmin_val
when we see a smaller value) is a hallmark of the greedy approach.State Tracking: We maintain and update certain ‘state’ variables (
min_val
andmax_diff
) as we progress through the array.
While the problem’s solution may primarily hinge on the concepts of “Running Minimum” and “Running Maximum Difference”, these other conceptual building blocks also play crucial roles in forming a complete, working solution.
Abstract Representation of the Problem
Formulating an abstract representation can help in identifying the underlying structure and recognizing similar problems.
Here’s an abstract representation of this problem:
Given a sequence of integers, find the maximum positive difference between two elements such that the smaller element comes before the larger element in the sequence. If there is no such pair of elements, return a specific value to indicate this.
Key elements:
 The sequence of integers, which we traverse in a linear manner.
 The “maximum positive difference” we’re looking to identify, which is analogous to a running maximum difference.
 The condition that the smaller element must come before the larger one, which introduces the concept of order.
 The return value when there’s no valid pair, which provides a way to handle edge cases.
In this abstract representation, we’ve stripped away the specific realworld context and focused on the structural essence of the problem. We can see how this formulation could apply to various scenarios beyond stock prices or the specific number array given in this problem.
Drills
Exercise 1  Working with lists in Python:
We use a loop to iterate over each element in the list and print it.
1 2 3
def print_list(nums): for num in nums: print(num)
Exercise 2  Find the minimum value in a list:
We initialize a variable
minimum
with the first element in the list, then iterate over the list. If we encounter a number smaller thanminimum
, we updateminimum
.1 2 3 4 5 6
def find_minimum(nums): minimum = nums[0] for num in nums: if num < minimum: minimum = num return minimum
Exercise 3  Find the maximum difference in a list:
We initialize a variable
max_difference
as zero, then use a nested loop to find the maximum difference between any two numbers.1 2 3 4 5 6 7
def find_max_difference(nums): max_difference = 0 for i in range(len(nums)): for j in range(i+1, len(nums)): if nums[j]  nums[i] > max_difference: max_difference = nums[j]  nums[i] return max_difference
Exercise 4  Combining the concepts:
Here we use the concepts from the previous exercises. We keep track of the minimum value found so far and the maximum difference found so far. By iterating only once through the list, we achieve a much more efficient solution than in Exercise 3.
1 2 3 4 5 6 7 8 9
def maximum_difference(nums): min_value = nums[0] max_difference = 1 for i in range(1, len(nums)): if nums[i] > min_value: max_difference = max(max_difference, nums[i]  min_value) else: min_value = nums[i] return max_difference
Please note that in Exercise 4, we return 1 when no maximum difference is found according to the problem’s requirement. This is different from Exercise 3 where we returned 0 when no difference was found.
Q&A
Is this an example of sliding window?
No, this is not an example of the sliding window technique. The sliding window technique typically involves maintaining a ‘window’ of elements in an array or list that moves, or ‘slides’, over the course of the algorithm. The window’s size might remain fixed or vary depending on the problem’s requirements.
In this problem, we are not maintaining a window of elements. Instead, we are traversing the entire array once, tracking the minimum value found so far and the maximum difference found so far. These two variables (min_val
and max_diff
) are updated as needed while scanning through the array, but they do not represent a ‘window’ of elements in the array.
Exactly the same code as “best time to buy and sell stocks”. Do you agree?
Yes, I agree. The logic behind this problem is indeed very similar to the “Best Time to Buy and Sell Stocks” problem. Both problems require finding the maximum difference between two numbers in an array where the smaller number comes before the larger one.
In “Best Time to Buy and Sell Stocks”, the numbers are prices of a stock, and you’re trying to maximize your profit by choosing the best time to buy (the lowest price) and sell (the highest price after the buy).
Here, the problem is abstracted a bit more, but the core idea remains the same: find the largest difference between two numbers where the smaller number appears before the larger one in the array. The same technique of maintaining a running minimum and a running maximum difference can be used to solve both problems efficiently.
Similar Problems
Here are 10 distinct problems that use similar underlying concepts:
LeetCode 121  Best Time to Buy and Sell Stock: This problem involves finding the maximum difference in an array of prices, akin to our problem.
LeetCode 53  Maximum Subarray: It also involves finding a maximum difference (sum in this case) within an array.
LeetCode 152  Maximum Product Subarray: This problem adds a twist by looking for a maximum product instead of a sum, but it still involves traversing an array with a running tally.
LeetCode 134  Gas Station: This problem is about finding a start point in a circular tour where we have to find a surplus of gas over cost. Similar concept of iterating through array and keep track of minimum and maximum.
LeetCode 918  Maximum Sum Circular Subarray: This problem involves finding the maximum sum in a circular array. It uses similar concepts of keeping track of running sum.
LeetCode 739  Daily Temperatures: It requires tracking a running maximum, similar to our problem.
LeetCode 11  Container With Most Water: This problem is about finding two lines, which, together with the xaxis, forms a container that would hold the greatest amount of water. This is another form of maximum difference problem.
LeetCode 84  Largest Rectangle in Histogram: It involves finding the largest rectangle within a histogram, a problem of maximum area which can be broken down similarly to our maximum difference problem.
LeetCode 209  Minimum Size Subarray Sum: This problem requires finding the smallest contiguous subarray with a sum greater than a given value. It uses a similar approach of iterating through an array and maintaining a running tally.
LeetCode 42  Trapping Rain Water: This problem is about calculating the amount of rain water trapped between buildings, which involves maintaining running left and right maximums, similar to our running minimum in the solved problem.