Skip to main content
Talentd

Find the Value of the Partition - Solution & Explanation

MediumArraySorting13 min read
Practice this problem

Problem Statement

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

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.

The C solution first sorts the input array. Then, it iterates through the sorted array, calculating differences between consecutive elements, and returns the smallest difference, which would represent the optimal partition value.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, and Space Complexity: O(1) for 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.

The C solution sorts the array and uses two pointers to find the minimum difference between consecutive elements after sorting, ensuring the partitions always remain valid and non-empty.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sort and Partition Using Breakpoint

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

Two-Pointer Technique on Array

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

Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Partition CheckO(n^2)O(1)Educational baseline to verify logic by checking every split
Sort and Adjacent DifferenceO(n log n)O(1) or O(n) depending on sortGeneral case; simplest and most common solution
Two-Pointer Scan After SortingO(n log n)O(1)When emphasizing partition boundaries using two pointers

Video Solution

6890. Find the Value of the Partition | Leetcode | Weekly Contest 350 | Solution Code. • Optimization • 638 views views

Watch 7 more video solutions →

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.

Ready to solve this problem?

Practice Find the Value of the Partition with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays