LeetCode Problem 2740

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

LeetCode 2740: Find the Value of the Partition

Problem Understanding

We are given an array nums containing positive integers. Our task is to divide all elements into two non-empty groups, nums1 and nums2.

Every element must belong to exactly one of the two groups, and neither group may be empty.

For a particular partition, the value is defined as:

$$|max(nums1) - min(nums2)|$$

The goal is to find the minimum possible value among all valid partitions.

The input is simply an array of positive integers. The output is a single integer representing the smallest achievable partition value.

The constraints are important:

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

The array can contain up to one hundred thousand elements, which means any solution that examines all possible partitions is infeasible. Since 2^n partitions exist in general, we need a much more efficient approach.

Several edge cases are worth considering immediately:

• Arrays containing only two elements.
• Arrays with duplicate values.
• Arrays where all values are identical.
• Arrays with very large values near 10^9.
• Arrays that are already sorted or completely unsorted.

The problem guarantees that the array contains at least two elements, so a valid partition always exists.

Approaches

Brute Force

A straightforward approach would be to consider every possible way to split the elements into two non-empty groups.

For each partition, we would compute:

• max(nums1)
• min(nums2)
• |max(nums1) - min(nums2)|

and keep the minimum value encountered.

This approach is correct because it explicitly checks every valid partition. However, an array of length n has 2^n possible assignments of elements to groups. After excluding invalid partitions where one group is empty, the number of possibilities remains exponential.

With n = 100000, such a solution is completely impractical.

Key Insight

Suppose we sort the array:

$$a_0 \le a_1 \le a_2 \le \cdots \le a_{n-1}$$

Consider any partition.

Let:

• x = max(nums1)
• y = min(nums2)

If x > y, then:

$$|x-y| = x-y$$

Since both values come from the sorted array, there must be elements between them in sorted order.

Observe that if there exists an adjacent pair in the sorted array with a smaller difference, we can create a partition whose value is exactly that adjacent difference.

More importantly, the minimum possible absolute difference between any two elements in a sorted array is always achieved by some adjacent pair.

Therefore, the optimal partition value equals the minimum difference between consecutive elements in the sorted array.

After sorting, we simply compute:

$$\min(a_i - a_{i-1})$$

for all adjacent pairs.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n · n)	O(n)	Examines every possible partition
Optimal	O(n log n)	O(1) extra or O(log n) sorting overhead	Sort and find minimum adjacent difference

Algorithm Walkthrough

1. Sort the array in non-decreasing order.

Sorting places numerically close values next to each other. Since we want the smallest possible absolute difference between a maximum and a minimum across a partition boundary, sorted order reveals the best candidates. 2. Initialize a variable answer with a very large value.

This variable will track the minimum adjacent difference found so far. 3. Iterate through the sorted array from index 1 to n - 1.

For each position, compute the difference between the current element and the previous element. 4. Update answer whenever a smaller difference is found.

Since the array is sorted, every difference is non-negative. 5. Return answer.

This minimum adjacent difference is the smallest possible partition value.

Why it works

After sorting, consider the adjacent pair that has the smallest difference, say a[i-1] and a[i].

Create a partition where:

• All elements up to index i-1 belong to nums1
• All elements from index i onward belong to nums2

Then:

• max(nums1) = a[i-1]
• min(nums2) = a[i]

The partition value becomes:

$$a[i] - a[i-1]$$

Since the minimum difference between any two elements in a sorted array must occur between adjacent elements, no partition can produce a smaller value. Therefore, the minimum adjacent difference is exactly the answer.

Problem Understanding

The problem asks us to split a given array nums into two non-empty subarrays, nums1 and nums2, such that every element belongs to exactly one of the two groups. For any such partition, we compute a value defined as the absolute difference between the maximum element of nums1 and the minimum element of nums2, written as:

$$| \max(nums1) - \min(nums2) |$$

Our goal is to choose a partition that minimizes this value.

In simpler terms, we are trying to split the array into two groups so that the “gap” between the largest element on the left group and the smallest element on the right group is as small as possible.

The input is an integer array nums with size between 2 and 100,000, and values up to 1e9. These constraints indicate that an O(n²) or worse solution will not work. We need at least O(n log n) or O(n) time.

Important observations and edge cases include arrays with only two elements, arrays already nearly sorted, and arrays with duplicates. Because all elements must be assigned to one of the two groups and both groups must be non-empty, every valid partition is essentially a “cut” in the array after arranging it in some order.

Approaches

Brute Force Approach

A naive solution would try every possible way to split the array into two non-empty subsets. For each subset assignment, we compute the maximum of one group and the minimum of the other, then evaluate the partition value.

However, this approach is infeasible because the number of possible partitions is $2^n - 2$, which is exponential. Even restricting to “prefix-suffix” splits after sorting still leads us to a simpler structure, but brute forcing subsets is unnecessary.

Key Insight

The critical observation is that the value depends only on the boundary between two groups, specifically between the maximum of one side and minimum of the other. If we sort the array, the best partition will always occur between two adjacent elements in the sorted array.

This is because any optimal split must separate smaller values from larger values. If we sort the array, the best possible partition is achieved by choosing an index i such that:

• nums1 = sorted[0:i]
• nums2 = sorted[i:]

Then:

• max(nums1) = sorted[i-1]
• min(nums2) = sorted[i]

So the answer reduces to minimizing:

$$sorted[i] - sorted[i-1]$$

over all valid i.

This transforms the problem into finding the minimum adjacent difference in a sorted array.

Comparison Table

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n · n)	O(1)	Try all partitions, infeasible for constraints
Optimal	O(n log n)	O(1) or O(n)	Sort and check adjacent differences

Algorithm Walkthrough

1. First, sort the input array. Sorting is essential because it groups close values together, ensuring that the smallest possible difference between potential partition boundaries becomes adjacent in the array. Without sorting, we cannot reliably identify optimal split points.
2. Initialize a variable answer to a large value. This will store the minimum partition value found across all possible valid splits.
3. Iterate through the sorted array starting from index 1 up to the end. At each index i, consider splitting the array into two parts: left side ending at i-1 and right side starting at i.
4. For each split point i, compute the difference between the current element and the previous element, which is sorted[i] - sorted[i-1]. This represents the partition value if we split exactly at this boundary.
5. Update the answer with the minimum value encountered so far.
6. After finishing the loop, return answer as the result.

Why it works

The correctness comes from the fact that in a sorted array, any partition that does not align with adjacent elements will produce a gap larger than or equal to at least one adjacent pair. Therefore, the minimum possible value of $|\max(nums1) - \min(nums2)|$ must correspond to the smallest difference between two consecutive elements in sorted order.

Python Solution

from typing import List

class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int:
        nums.sort()

        answer = float("inf")

        for i in range(1, len(nums)):
            answer = min(answer, nums[i] - nums[i - 1])

        return answer

The implementation begins by sorting the array. Once sorted, any pair of elements that could potentially produce the minimum partition value must appear as adjacent elements.

The variable answer stores the smallest adjacent difference seen so far.

The loop scans all consecutive pairs in the sorted array and computes their difference. Because the array is sorted, each difference is non-negative.

Whenever a smaller difference is found, answer is updated.

After all adjacent pairs have been processed, answer contains the minimum possible partition value and is returned.

    ans = float('inf')
    
    for i in range(1, len(nums)):
        ans = min(ans, nums[i] - nums[i - 1])
    
    return ans

### Implementation Explanation

The solution begins by sorting the array, which ensures that any optimal partition boundary will occur between adjacent elements. We then iterate once through the sorted array, computing differences between consecutive elements. Each difference represents a valid partition value if we split at that point. We maintain the minimum of these differences, which becomes the final answer. This directly implements the insight that the optimal partition is determined by the closest pair of adjacent values in sorted order.

## Go Solution

```go
import "sort"

func findValueOfPartition(nums []int) int {
	sort.Ints(nums)

	answer := nums[1] - nums[0]

	for i := 2; i < len(nums); i++ {
		diff := nums[i] - nums[i-1]
		if diff < answer {
			answer = diff
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version.

The array is sorted using sort.Ints. After sorting, the minimum adjacent difference is computed through a single linear scan.

Since all values are at most 10^9, the difference between two elements easily fits within Go's int type on LeetCode platforms. No special overflow handling is required.

Worked Examples

Example 1

Input

nums = [1,3,2,4]

Step 1: Sort

[1,2,3,4]

Step 2: Compute Adjacent Differences

i	Pair	Difference	Current Answer
1	(1,2)	1	1
2	(2,3)	1	1
3	(3,4)	1	1

Result

1

One corresponding partition is:

nums1 = [1,2]
nums2 = [3,4]

Then:

max(nums1) = 2
min(nums2) = 3
value = |2 - 3| = 1

Example 2

Input

nums = [100,1,10]

Step 1: Sort

[1,10,100]

Step 2: Compute Adjacent Differences

i	Pair	Difference	Current Answer
1	(1,10)	9	9
2	(10,100)	90	9

Result

9

One corresponding partition is:

nums1 = [1]
nums2 = [10,100]

Then:

max(nums1) = 1
min(nums2) = 10
value = 9

The same minimum value can also be achieved by:

nums1 = [10]
nums2 = [1,100]

giving:

|10 - 1| = 9

sort.Ints(nums)

ans := nums[1] - nums[0]

for i := 2; i < len(nums); i++ {
    diff := nums[i] - nums[i-1]
    if diff < ans {
        ans = diff
    }
}

return ans

}

### Go-specific Notes

In Go, we use `sort.Ints` to sort the slice in-place. We initialize `ans` using the first adjacent difference to avoid dealing with a sentinel infinity value. Since Go integers are safe within the given constraints (values up to 1e9), there is no overflow concern when subtracting adjacent elements. Slice handling is straightforward since Go slices are reference types, and sorting modifies the original slice directly.

## Worked Examples

### Example 1: nums = [1,3,2,4]

After sorting:

`[1, 2, 3, 4]`

We compute adjacent differences:

| i | nums[i-1] | nums[i] | Difference |
| --- | --- | --- | --- |
| 1 | 1 | 2 | 1 |
| 2 | 2 | 3 | 1 |
| 3 | 3 | 4 | 1 |

Minimum difference is 1.

So answer = 1.

### Example 2: nums = [100,1,10]

After sorting:

`[1, 10, 100]`

Adjacent differences:

| i | nums[i-1] | nums[i] | Difference |
| --- | --- | --- | --- |
| 1 | 1 | 10 | 9 |
| 2 | 10 | 100 | 90 |

Minimum difference is 9.

So answer = 9.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(n log n) | Sorting dominates the running time |
| Space | O(1) extra or O(log n) sorting overhead | Aside from sorting internals, only a few variables are used |

The linear scan after sorting requires only `O(n)` time. Since sorting requires `O(n log n)` time, it becomes the dominant operation.

The algorithm itself uses constant additional storage. Depending on the language implementation, the sorting routine may use a small amount of auxiliary stack space.

## Test Cases

```python
from typing import List

s = Solution()

assert s.findValueOfPartition([1, 3, 2, 4]) == 1      # example 1
assert s.findValueOfPartition([100, 1, 10]) == 9      # example 2

assert s.findValueOfPartition([1, 2]) == 1            # minimum length
assert s.findValueOfPartition([5, 5]) == 0            # two identical values

assert s.findValueOfPartition([4, 4, 4, 4]) == 0      # all identical
assert s.findValueOfPartition([1, 1000000000]) == 999999999  # large values

assert s.findValueOfPartition([8, 1, 6, 3]) == 2      # unsorted input
assert s.findValueOfPartition([1, 2, 2, 10]) == 0     # duplicate values

assert s.findValueOfPartition([10, 20, 30, 40, 50]) == 10   # evenly spaced
assert s.findValueOfPartition([7, 2, 9, 3, 5]) == 1         # minimum gap in middle

assert s.findValueOfPartition([100, 101, 200, 300]) == 1    # smallest adjacent gap

Test Summary

Test	Why
[1,3,2,4]	Official example
[100,1,10]	Official example
[1,2]	Smallest valid input size
[5,5]	Two equal elements
[4,4,4,4]	All values identical
[1,1000000000]	Maximum value range
[8,1,6,3]	Unsorted input
[1,2,2,10]	Duplicate values create answer 0
[10,20,30,40,50]	Uniform gaps
[7,2,9,3,5]	Minimum gap appears in middle
[100,101,200,300]	Smallest adjacent pair determines answer

Edge Cases

Arrays Containing Duplicate Values

A common source of mistakes is forgetting that duplicate values can exist. If two equal values appear in the array, the minimum adjacent difference after sorting becomes zero.

For example:

[1, 2, 2, 10]

After sorting:

[1, 2, 2, 10]

The adjacent pair (2, 2) has difference 0, so the answer is 0. The implementation naturally handles this because it checks every adjacent pair.

Minimum Array Length

When nums.length == 2, there is only one possible partition boundary after sorting.

Example:

[5, 8]

The sorted array remains:

[5, 8]

The only adjacent difference is 3, which is returned. The implementation correctly processes this case because the loop begins at index 1.

Very Large Values

The values may be as large as 10^9.

Example:

[1, 1000000000]

The difference is:

999999999

This still fits comfortably within standard integer types used by both Python and Go. The algorithm performs only subtraction and comparison operations, so no overflow issues arise under the given constraints.

Already Sorted or Reverse Sorted Input

The input order does not matter because the first step is sorting.

For example:

[5,4,3,2,1]

becomes:

[1,2,3,4,5]

and the algorithm proceeds normally. This guarantees correctness regardless of the original arrangement of elements. | Time | O(n log n) | Sorting dominates, linear scan afterward | | Space | O(1) or O(n) | Depending on sorting implementation |

The dominant cost is sorting the array. Once sorted, we perform a single pass to compute adjacent differences, which is linear.

Test Cases

assert Solution().findValueOfPartition([1, 3, 2, 4]) == 1  # normal case
assert Solution().findValueOfPartition([100, 1, 10]) == 9  # unsorted input
assert Solution().findValueOfPartition([1, 2]) == 1  # minimum size array
assert Solution().findValueOfPartition([5, 5, 5, 5]) == 0  # duplicates
assert Solution().findValueOfPartition([1, 1000000000]) == 999999999  # large range
assert Solution().findValueOfPartition([8, 1, 6, 9]) == 1  # mixed order

Test	Why
[1, 3, 2, 4]	Standard case with clear optimal split
[100, 1, 10]	Requires sorting before reasoning
[1, 2]	Minimum valid input size
[5, 5, 5, 5]	All duplicates, checks zero difference
[1, 1e9]	Maximum value gap stress test
[8, 1, 6, 9]	Random order ensures correctness after sort

Edge Cases

One important edge case is when the array has exactly two elements. In this situation, there is only one possible partition, so the result is simply the absolute difference between those two values. The algorithm handles this correctly because sorting still produces two elements and the single adjacent difference is returned.

Another edge case occurs when all elements are identical. In this case, every adjacent difference is zero after sorting, and the algorithm correctly returns zero. This is important because it verifies that duplicates do not introduce instability or incorrect partitioning logic.

A further edge case involves large numerical ranges, such as values close to 1e9. The subtraction still works safely within integer limits, and since we only compare differences, there is no risk of overflow in Python or Go. The algorithm correctly identifies the smallest gap regardless of magnitude.