Abstract / Summary

Find the largest difference between two numbers in an array by picking one from the start and one from the end.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 61% (200k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Search
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method maxDistance that receives two integer lists, nums1 and nums2. The goal of the method is to compute the largest possible index distance j - i such that i is a valid index in nums1, j is a valid index in nums2, i ≤ j, and the element at i in nums1 does not exceed the element at j in nums2. The algorithm walks through nums2 with an outer index j while maintaining a monotonic pointer i into nums1. By advancing i only when necessary, the method avoids redundant comparisons and directly evaluates candidate distances.

Key Steps

The algorithm can be broken down into three essential phases: initialization, iterative scanning with conditional advancement, and result updating.

Initialization

At the start, the method creates a variable result set to zero, which will hold the maximum distance found. It also declares an index i initialized to zero, representing the current candidate position in nums1.

result = 0
i = 0

Iterative Scanning

The outer loop iterates over every possible j index in nums2. For each j, a nested while loop moves the i pointer forward while three conditions hold: i has not reached the penultimate element of nums1, i is still less than j, and the element at nums1[i] is greater than the element at nums2[j]. This loop ensures that i points to the leftmost position that satisfies the required inequality for the current j.

for j in range(len(nums2)):
    while i < len(nums1) - 1 and i < j and nums1[i] > nums2[j]:
        i += 1

Distance Evaluation

After the inner loop finishes, the algorithm checks whether the current pair (i, j) meets the condition nums1[i] <= nums2[j]. If it does, the distance j - i is computed and compared with the current result. The larger of the two values becomes the new result.

if nums1[i] <= nums2[j]:
    distance = j - i
    result = max(result, distance)

Finally, the method returns the accumulated maximum distance.

return result

Edge Cases Handled

The code gracefully handles several boundary situations without explicit special-case logic.

When nums1 contains only one element, the condition i < len(nums1) - 1 prevents the inner loop from attempting to advance i beyond the sole index, thereby avoiding an out-of-range scenario.

If j is smaller than i during iteration, the i < j guard in the while condition stops any further movement of i, ensuring that the required ordering i ≤ j is never violated.

When all elements of nums1 are larger than every element of nums2, the inner loop will push i as far right as allowed (up to the second-last index). The subsequent if test will fail for every j, leaving result at its initial value of zero, which correctly reflects that no valid pair exists.

Conversely, if every element of nums1 is less than or equal to every element of nums2, the inner loop never increments i, and the distance calculation uses the full span from the start of nums1 to each j. The maximum distance will then be the difference between the last index of nums2 and the first index of nums1, which the algorithm captures.

The loop bounds (len(nums2) for j and len(nums1) - 1 for the inner condition) guarantee that both indices stay within the valid range of their respective lists throughout execution.

Performance Optimizations

The primary optimization stems from the single forward movement of the pointer i. Because i never moves backward, each element of nums1 is examined at most once across the entire execution. This monotonic progression eliminates the need for nested full scans, reducing the total number of element comparisons dramatically compared with a naïve double-loop approach.

By checking i < len(nums1) - 1 before accessing nums1[i], the code avoids an unnecessary boundary check inside the loop body, allowing the interpreter to skip the final element of nums1 when it is not needed for further advancement.

The use of the built-in max function to update result provides a concise and efficient way to keep track of the best distance without additional conditional branches.

Overall, the algorithm leverages a two-pointer technique that aligns with the sorted-like nature of the problem constraints, ensuring that each list is traversed in linear time while maintaining constant auxiliary storage.

Imagine you have two long rows of colorful building blocks laid out on the floor. Each block has a number written on it. Some blocks have big numbers and some have small numbers. You have a special mission to pick one block from the first row and one block from the second row to see how far apart they are.

The code starts by looking at the very first block in each row. It moves along the second row one step at a time, just like a little toy car driving down a track. While the car drives, it keeps checking the first row to see if it can find a pair of blocks that match the rule. To follow the rule, the block in the first row must have a number that is smaller than or the same size as the block in the second row.

If the block in the first row is too big, the helper advances to look at the next block in that row to find a better fit. Once a good pair is found, the code measures the space between the two blocks by counting how many steps are between them. It remembers the biggest space found so far and keeps that giant number in a special spot. It repeats this for every single block in the second row until it reaches the very end of the line.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java	Python					TS
	WalkCCC	C++		Java	Python
	leetcode.ca	C++	JS	Java	Python			Go	Rust	TS
	Progiez	C++		Java	Python
github	AdelDaniel					Dart
	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	haoel	C++
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM						C#
	varunu28			Java
	withaarzoo	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, Rust, TypeScript
Progiez	C++, Java, Python
AdelDaniel	Dart
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
haoel	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
withaarzoo	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality