2740. Find the Value of the Partition - Solution

Q: Is Find the Value of the Partition easy or hard?

The problem is rated Medium on LeetCode but conceptually straightforward once the sorting insight is recognized. The main challenge is realizing that the optimal partition must occur between adjacent elements in the sorted array.

Q: Find the Value of the Partition Python/Java solution

In Python or Java, sort the array using the built-in sorting method and iterate once to compute nums[i+1] - nums[i]. Track the minimum difference during the loop and return it as the answer. The implementation is typically under 10 lines.

Q: How to solve Find the Value of the Partition in O(n)?

A true O(n) solution is generally not possible with arbitrary integers because ordering is required to determine the best partition. The practical optimal approach sorts the array in O(n log n) time and then performs a linear pass to compute adjacent differences.

Q: What is the best approach for Find the Value of the Partition?

The best approach sorts the array and computes the minimum difference between adjacent elements. After sorting, a valid partition occurs between indices i and i+1, where max(left) = nums[i] and min(right) = nums[i+1]. Scanning these differences gives the minimum partition value in O(n log n) time.

Q: Is Find the Value of the Partition asked at Google/Amazon/Meta?

Partitioning and minimum-difference array problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying pattern of sorting and analyzing adjacent elements is a common interview technique.

Q: What data structure is used in Find the Value of the Partition?

The solution primarily uses an array and a sorting algorithm. After sorting, the algorithm performs a linear scan across the array to evaluate adjacent differences, sometimes framed using a two-pointer traversal.

Q: What is the time complexity of Find the Value of the Partition?

The optimal solution runs in O(n log n) time because sorting dominates the runtime. After sorting, a single linear scan calculates the minimum difference between adjacent elements in O(n). Space complexity is O(1) if the sort is in-place.

The 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 <= 10⁵
1 <= nums[i] <= 10⁹

Approach overview

Problem Overview: You are given an integer array and must split it into two non‑empty partitions. The partition value is defined as |max(left) - min(right)|. The goal is to choose the split that minimizes this value.

The key observation: if the array is ordered, the optimal split always happens between two adjacent numbers. Once sorted, the maximum of the left side becomes nums[i] and the minimum of the right side becomes nums[i+1]. The problem reduces to finding the smallest difference between neighboring elements.

Approach 1: Sort and Partition Using Breakpoint (O(n log n) time, O(1) extra space)

Sort the array first using any comparison sort. After sorting, iterate once through the array and compute nums[i+1] - nums[i] for every adjacent pair. Each pair represents a potential partition where the left side contains elements up to i and the right side starts at i+1. Track the minimum difference encountered during the scan. Sorting ensures that all elements in the left partition are less than or equal to those in the right partition, so the absolute value is unnecessary. This approach is straightforward and relies on properties of ordered data, making it the most common interview solution when working with arrays and sorting.

Approach 2: Two-Pointer Scan on the Sorted Array (O(n log n) time, O(1) space)

After sorting the array, maintain two pointers left and right where right = left + 1. Move both pointers forward while computing the difference between the two positions. The pointers effectively represent the boundary between the two partitions. This framing highlights the partition boundary explicitly and mirrors common two‑pointer patterns used in array problems. The minimum difference found during this linear scan is the final answer.

Recommended for interviews: The expected approach is sorting followed by a single pass to check adjacent differences. Explaining the reasoning behind why the optimal partition must occur between neighboring elements in the sorted array demonstrates strong algorithmic intuition. A brute force check of every possible partition shows understanding, but recognizing the sorted adjacency insight and reducing the problem to a single pass shows stronger problem‑solving skills.

Approach 1: Sort and Partition Using Breakpoint

When the array is sorted, the differences between adjacent elements determine potential partitions. The optimal partition can be found by assessing the smallest difference between consecutive elements, which ensures both partitions are non-empty.

Python

def min_partition_value(nums):
    nums.sort()
    min_difference = abs(nums[1] - nums[0])
    for i in range(1, len(nums) - 1):
        min_difference = min(min_difference, abs(nums[i + 1] - nums[i]))
    return min_difference

nums = [1, 3, 2, 4]
print(min_partition_value(nums))

Java

import java.util.Arrays;

public class PartitionValue {
    public static int minPartitionValue(int[] nums) {
        Arrays.sort(nums);
        int minDifference = Math.abs(nums[1] - nums[0]);
        for (int i = 1; i < nums.length - 1; i++) {
            minDifference = Math.min(minDifference, Math.abs(nums[i + 1] - nums[i]));
        }
        return minDifference;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 4};
        System.out.println(minPartitionValue(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int minPartitionValue(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    int minDifference = std::abs(nums[1] - nums[0]);
    for (size_t i = 1; i < nums.size() - 1; ++i) {
        minDifference = std::min(minDifference, std::abs(nums[i + 1] - nums[i]));
    }
    return minDifference;
}

int main() {
    std::vector<int> nums = {1, 3, 2, 4};
    std::cout << minPartitionValue(nums) << std::endl;
    return 0;
}

JavaScript

function minPartitionValue(nums) {
    nums.sort((a, b) => a - b);
    let minDifference = Math.abs(nums[1] - nums[0]);
    for (let i = 1; i < nums.length - 1; i++) {
        minDifference = Math.min(minDifference, Math.abs(nums[i + 1] - nums[i]));
    }
    return minDifference;
}

const nums = [1, 3, 2, 4];
console.log(minPartitionValue(nums));

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int minPartitionValue(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    int minDifference = abs(nums[1] - nums[0]);
    for (int i = 1; i < numsSize - 1; i++) {
        int currentDifference = abs(nums[i + 1] - nums[i]);
        if (currentDifference < minDifference) {
            minDifference = currentDifference;
        }
    }
    return minDifference;
}

int main() {
    int nums[] = {1, 3, 2, 4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", minPartitionValue(nums, numsSize));
    return 0;
}

using System;

public class PartitionValue {
    public static int MinPartitionValue(int[] nums) {
        Array.Sort(nums);
        int minDifference = Math.Abs(nums[1] - nums[0]);
        for (int i = 1; i < nums.Length - 1; i++) {
            minDifference = Math.Min(minDifference, Math.Abs(nums[i + 1] - nums[i]));
        }
        return minDifference;
    }

    public static void Main() {
        int[] nums = {1, 3, 2, 4};
        Console.WriteLine(MinPartitionValue(nums));
    }
}

The Python solution sorts the input list and finds the minimal difference between adjacent sorted numbers for the optimal partition value.

Complexity

Time Complexity: O(n log n), due to sorting. Space Complexity: O(1), assuming in-place operations.

Try this approach in the editor

Approach 2: Two-Pointer Technique on Array

This approach utilizes two pointers after sorting the array. Begin with the two pointers dividing the array into two parts, adjusting the pointers as necessary to minimize the partition value. The approach ensures each partition is non-empty while calculating the optimal value.

Python

def min_partition_value(nums):
    nums.sort()
    min_difference = abs(nums[1] - nums[0])
    for i in range(1, len(nums) - 1):
        min_difference = min(min_difference, abs(nums[i + 1] - nums[i]))
    return min_difference

nums = [1, 3, 2, 4]
print(min_partition_value(nums))

Java

import java.util.Arrays;

public class PartitionValue {
    public static int minPartitionValue(int[] nums) {
        Arrays.sort(nums);
        int left = 0, right = 1, minDifference = Math.abs(nums[right] - nums[left]);
        while (right < nums.length) {
            int currentDifference = Math.abs(nums[right] - nums[left]);
            if (currentDifference < minDifference) {
                minDifference = currentDifference;
            }
            left++;
            right++;
        }
        return minDifference;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 4};
        System.out.println(minPartitionValue(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int minPartitionValue(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    int minDifference = std::abs(nums[1] - nums[0]);
    for (size_t i = 1; i < nums.size() - 1; i++) {
        minDifference = std::min(minDifference, std::abs(nums[i + 1] - nums[i]));
    }
    return minDifference;
}

int main() {
    std::vector<int> nums = {1, 3, 2, 4};
    std::cout << minPartitionValue(nums) << std::endl;
    return 0;
}

JavaScript

function minPartitionValue(nums) {
    nums.sort((a, b) => a - b);
    let minDifference = Math.abs(nums[1] - nums[0]);
    for (let i = 1; i < nums.length - 1; i++) {
        minDifference = Math.min(minDifference, Math.abs(nums[i + 1] - nums[i]));
    }
    return minDifference;
}

const nums = [1, 3, 2, 4];
console.log(minPartitionValue(nums));

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int minPartitionValue(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    int left = 0, right = 1, minDifference = abs(nums[right] - nums[left]);
    while (right < numsSize) {
        int currentDifference = abs(nums[right] - nums[left]);
        if (currentDifference < minDifference) {
            minDifference = currentDifference;
        }
        left++;
        right++;
    }
    return minDifference;
}

int main() {
    int nums[] = {1, 3, 2, 4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", minPartitionValue(nums, numsSize));
    return 0;
}

using System;

public class PartitionValue {
    public static int MinPartitionValue(int[] nums) {
        Array.Sort(nums);
        int left = 0, right = 1, minDifference = Math.Abs(nums[right] - nums[left]);
        while (right < nums.Length) {
            int currentDifference = Math.Abs(nums[right] - nums[left]);
            if (currentDifference < minDifference) {
                minDifference = currentDifference;
            }
            left++;
            right++;
        }
        return minDifference;
    }

    public static void Main() {
        int[] nums = {1, 3, 2, 4};
        Console.WriteLine(MinPartitionValue(nums));
    }
}

In Python, the solution revolves around sorting followed by pointer adjustments to determine the minimal partition value effectively.

Complexity

Time Complexity: O(n log n), Space Complexity: O(1).

Try this approach in the editor

Approach 3: Sorting

The problem requires us to minimize the partition value. Therefore, we can sort the array and then take the minimum difference between two adjacent numbers.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array.

TypeScript

function findValueOfPartition(nums: number[]): number {
    nums.sort((a, b) => a - b);
    let ans = Infinity;
    for (let i = 1; i < nums.length; ++i) {
        ans = Math.min(ans, Math.abs(nums[i] - nums[i - 1]));
    }
    return ans;
}

func findValueOfPartition(nums []int) int {
	sort.Ints(nums)
	ans := 1 << 30
	for i, x := range nums[1:] {
		ans = min(ans, x-nums[i])
	}
	return ans
}

Rust

impl Solution {
    pub fn find_value_of_partition(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let mut ans = i32::MAX;
        for i in 1..nums.len() {
            ans = ans.min(nums[i] - nums[i - 1]);
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sort and Partition Using Breakpoint	Time Complexity: O(n log n), due to sorting. Space Complexity: O(1), assuming in-place operations.
Two-Pointer Technique on Array	Time Complexity: O(n log n), Space Complexity: O(1).
Sorting	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Partition Check	O(n^2)	O(1)	Educational baseline to verify logic by checking every split
Sort and Adjacent Difference	O(n log n)	O(1) or O(n) depending on sort	General case; simplest and most common solution
Two-Pointer Scan After Sorting	O(n log n)	O(1)	When emphasizing partition boundaries using two pointers

Frequently asked questions

Is Find the Value of the Partition easy or hard?

The problem is rated Medium on LeetCode but conceptually straightforward once the sorting insight is recognized. The main challenge is realizing that the optimal partition must occur between adjacent elements in the sorted array.

Find the Value of the Partition Python/Java solution

In Python or Java, sort the array using the built-in sorting method and iterate once to compute nums[i+1] - nums[i]. Track the minimum difference during the loop and return it as the answer. The implementation is typically under 10 lines.

How to solve Find the Value of the Partition in O(n)?

A true O(n) solution is generally not possible with arbitrary integers because ordering is required to determine the best partition. The practical optimal approach sorts the array in O(n log n) time and then performs a linear pass to compute adjacent differences.

What is the best approach for Find the Value of the Partition?

The best approach sorts the array and computes the minimum difference between adjacent elements. After sorting, a valid partition occurs between indices i and i+1, where max(left) = nums[i] and min(right) = nums[i+1]. Scanning these differences gives the minimum partition value in O(n log n) time.

Is Find the Value of the Partition asked at Google/Amazon/Meta?

Partitioning and minimum-difference array problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying pattern of sorting and analyzing adjacent elements is a common interview technique.

What data structure is used in Find the Value of the Partition?

The solution primarily uses an array and a sorting algorithm. After sorting, the algorithm performs a linear scan across the array to evaluate adjacent differences, sometimes framed using a two-pointer traversal.

What is the time complexity of Find the Value of the Partition?

The optimal solution runs in O(n log n) time because sorting dominates the runtime. After sorting, a single linear scan calculates the minimum difference between adjacent elements in O(n). Space complexity is O(1) if the sort is in-place.

Find the Value of the Partition solution and explanation

The problem

Approach overview

Approach 1: Sort and Partition Using Breakpoint

Approach 2: Two-Pointer Technique on Array

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Value of the Partition solution and explanation

The problem

Approach overview

Approach 1: Sort and Partition Using Breakpoint

Approach 2: Two-Pointer Technique on Array

Approach 3: Sorting

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems