# Find the Value of the Partition
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-value-of-the-partition)
Canonical: https://scaleengineer.com/dsa/problems/find-the-value-of-the-partition
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given a **positive** integer array `nums`.

Partition `nums` into two arrays, `nums1` and `nums2`, such that:

* Each element of the array `nums` belongs to either the array `nums1` or the array `nums2`.
* Both arrays are **non-empty**.
* The value of the partition is **minimized**.

The value of the partition is `|max(nums1) - min(nums2)|`.

Here, `max(nums1)` denotes the maximum element of the array `nums1`, and `min(nums2)` denotes the minimum element of the array `nums2`.

Return _the integer denoting the value of such partition_.

**Example 1:**

**Input:** nums = [1,3,2,4]
**Output:** 1
**Explanation:** We can partition the array nums into nums1 = [1,2] and nums2 = [3,4].
- The maximum element of the array nums1 is equal to 2.
- The minimum element of the array nums2 is equal to 3.
The value of the partition is |2 - 3| = 1. 
It can be proven that 1 is the minimum value out of all partitions.

**Example 2:**

**Input:** nums = [100,1,10]
**Output:** 9
**Explanation:** We can partition the array nums into nums1 = [10] and nums2 = [100,1].
- The maximum element of the array nums1 is equal to 10.
- The minimum element of the array nums2 is equal to 1.
The value of the partition is |10 - 1| = 9.
It can be proven that 9 is the minimum value out of all partitions.

**Constraints:**

* `2 <= nums.length <= 105`
* `1 <= nums[i] <= 109`

# Approaches
## Brute Force by Generating All Partitions
This approach considers every single possible way to partition the `nums` array into two non-empty subarrays, `nums1` and `nums2`. For each valid partition, it computes the value `|max(nums1) - min(nums2)|` and keeps track of the minimum value encountered. This guarantees finding the optimal solution by sheer force of checking all possibilities.
**Time:** O(n * 2^n) - There are `2^n - 2` partitions. For each, we iterate through `n` elements to build the subarrays and then find the max/min, which also takes O(n) time. · **Space:** O(n) - To store the two subarrays for each partition.
**Pros:** It is a straightforward implementation of the problem definition.; Guaranteed to find the correct answer by exhaustively checking every possibility.
**Cons:** Extremely inefficient due to its exponential time complexity.; The approach will time out for the given constraints (`n` up to 10^5).
### Explanation
The method systematically generates all partitions of the input array `nums`. Since each of the `n` elements can go into one of two subarrays, there are `2^n` total possibilities. We can represent each partition using a bitmask of length `n`, where the `i`-th bit determines which subarray `nums[i]` belongs to. We must exclude the two cases where one subarray is empty (represented by bitmasks of all 0s or all 1s), leaving `2^n - 2` partitions to check.

For each of these partitions, we construct the two subarrays, find the maximum of the first and the minimum of the second, and calculate their absolute difference. The overall minimum of these values is the answer. While correct, this approach is computationally infeasible for anything but very small arrays.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int findValueOfPartition(int[] nums) {
        int n = nums.length;
        int minVal = Integer.MAX_VALUE;

        // Iterate through all possible partitions using a bitmask
        // from 1 to (1 << n) - 2 to ensure non-empty partitions.
        for (int i = 1; i < (1 << n) - 1; i++) {
            List<Integer> nums1 = new ArrayList<>();
            List<Integer> nums2 = new ArrayList<>();

            for (int j = 0; j < n; j++) {
                // Check if the j-th bit is set
                if ((i & (1 << j)) != 0) {
                    nums1.add(nums[j]);
                } else {
                    nums2.add(nums[j]);
                }
            }

            int max1 = Integer.MIN_VALUE;
            for (int x : nums1) {
                max1 = Math.max(max1, x);
            }

            int min2 = Integer.MAX_VALUE;
            for (int x : nums2) {
                min2 = Math.min(min2, x);
            }

            minVal = Math.min(minVal, Math.abs(max1 - min2));
        }
        return minVal;
    }
}
```
### Algorithm
- Initialize a variable `min_partition_value` to positive infinity.
- The number of elements is `n`. We can represent a partition with a bitmask of length `n`.
- Iterate through all possible bitmasks from `1` to `(1 << n) - 2`. This range ensures that both partitions `nums1` and `nums2` are non-empty.
- For each `mask`:
  - Create two empty lists, `nums1` and `nums2`.
  - Iterate from `j = 0` to `n-1`:
    - If the `j`-th bit is set in the `mask`, add `nums[j]` to `nums1`.
    - Otherwise, add `nums[j]` to `nums2`.
  - Find the maximum element in `nums1` (`max1`) and the minimum element in `nums2` (`min2`).
  - Calculate the current partition's value: `abs(max1 - min2)`.
  - Update `min_partition_value = min(min_partition_value, abs(max1 - min2))`.
- After checking all partitions, return `min_partition_value`.

## Sorting and Finding Minimum Adjacent Difference
A much more efficient and insightful approach is to realize that the partition value is minimized when `max(nums1)` and `min(nums2)` are as close as possible. The two numbers in the entire set `nums` that are closest in value must be adjacent to each other in a sorted version of the array. This approach leverages this fact by first sorting the array and then finding the minimum difference between any two adjacent elements.
**Time:** O(n log n) - This is dominated by the sorting step. The subsequent loop to find the minimum difference runs in O(n) time. · **Space:** O(log n) or O(n) - The space complexity depends on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitives uses a dual-pivot quicksort which takes O(log n) space on average for the recursion stack.
**Pros:** Highly efficient and optimal for the given constraints.; The implementation is simple and concise.; The logic correctly simplifies a complex partition problem into a simple array traversal.
**Cons:** The time complexity is limited by the sorting algorithm, so it's not a linear time solution.; Requires modifying the input array or using extra space for a sorted copy.
### Explanation
The key insight is that for any partition `(nums1, nums2)`, the value `|max(nums1) - min(nums2)|` will be the absolute difference between two elements from the original array. This difference will always be greater than or equal to the minimum difference between any two adjacent elements in the sorted version of `nums`.

Let the sorted array be `s_1, s_2, ..., s_n`. The minimum possible difference between any two distinct elements in the array is `min(s_{i+1} - s_i)` for `1 <= i < n`. Let's call this `d_min`.

We can always construct a partition that achieves this value. For instance, if `d_min = s_k - s_{k-1}`, we can set `nums1 = {s_1, ..., s_{k-1}}` and `nums2 = {s_k, ..., s_n}`. For this partition, `max(nums1) = s_{k-1}` and `min(nums2) = s_k`, and the value is `|s_{k-1} - s_k}| = d_min`.

Since we've shown that a partition with value `d_min` exists and that no partition can have a value smaller than `d_min`, the problem is reduced to finding this minimum adjacent difference.

```java
import java.util.Arrays;

class Solution {
    public int findValueOfPartition(int[] nums) {
        // Sort the array to bring elements with the smallest difference together.
        Arrays.sort(nums);
        
        int minDifference = Integer.MAX_VALUE;
        
        // Iterate through the sorted array to find the minimum difference
        // between any two adjacent elements.
        for (int i = 0; i < nums.length - 1; i++) {
            int difference = nums[i+1] - nums[i];
            minDifference = Math.min(minDifference, difference);
        }
        
        return minDifference;
    }
}
```
### Algorithm
- Sort the input array `nums` in non-decreasing order.
- Initialize a variable `min_difference` to a very large value (e.g., `Integer.MAX_VALUE`).
- Iterate through the sorted array from the first element to the second-to-last element (from index `i = 0` to `n-2`).
- In each iteration, calculate the difference between the adjacent elements: `difference = nums[i+1] - nums[i]`.
- Update `min_difference` with the smaller value between the current `min_difference` and the newly calculated `difference`.
- After the loop finishes, `min_difference` will hold the minimum possible partition value. Return `min_difference`.

# Solutions
### Java

```java
class Solution {
public
  int findValueOfPartition(int[] nums) {
    Arrays.sort(nums);
    int ans = 1 << 30;
    for (int i = 1; i < nums.length; ++i) {
      ans = Math.min(ans, nums[i] - nums[i - 1]);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findValueOfPartition(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int ans = 1 << 30;
    for (int i = 1; i < nums.size(); ++i) {
      ans = min(ans, nums[i] - nums[i - 1]);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findValueOfPartition(self, nums: List[int]) -> int: nums . sort() return min(b - a for a, b in pairwise(nums))

```