Get started

Divide Array Into Arrays With Max Difference — Medium Problem & Solution

You are given an array nums whose length is a multiple of 3, and an integer k.

  • Difficulty: Medium
  • Topics: Arrays, Greedy, Sorting
  • Asked at: Amazon, Flipkart
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an array nums whose length is a multiple of 3, and an integer k. Split every element into groups of exactly three so that in each group the difference between any two elements is at most k.

Return the groups, each group sorted ascending, and the groups themselves ordered by their smallest element. If no such split exists, return [].

Example 1

Input: nums = [1,3,4,8,7,9,3,5,1], k = 2
Output: [[1,1,3],[3,4,5],[7,8,9]]
Explanation: Every group spans at most 2.

Example 2

Input: nums = [2,4,2,2,5,2], k = 2
Output: []
Explanation: Sorted it reads 2,2,2,2,4,5 — the group 2,4,5 spans 3, and no arrangement does better.

Example 3

Input: nums = [4,2,9,8,2,12,7,12,10,5,8,5,5,7,9,2,5,11], k = 14
Output: [[2,2,2],[4,5,5],[5,5,7],[7,8,8],[9,9,10],[11,12,12]]

Constraints

  • nums.length is a multiple of 3
  • 3 <= nums.length <= 300
  • 1 <= nums[i] <= 100000
  • 1 <= k <= 100000

How to solve Divide Array Into Arrays With Max Difference

Sort, then take consecutive triples. Any valid split must group values that are close together, and sorted order already puts the closest values side by side — so if consecutive triples fail, nothing works.

Approach

  1. Sort nums ascending into s.
  2. Walk i in steps of three. The triple is s[i], s[i+1], s[i+2], already ascending.
  3. If s[i+2] - s[i] > k, return [] immediately.
  4. Otherwise append the triple and continue.

Why it works

Exchange argument: take any valid split and sort it; if some group is not three consecutive sorted elements, two groups interleave, and swapping the offending elements back into consecutive positions never increases either group's span. Repeating the swap reaches the consecutive-triple split, so it is valid whenever anything is.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • Comparing only neighbouring pairs inside a triple misses the first-to-last span, which is the real constraint.
  • Returning partial groups before discovering a failing triple — the answer is all-or-nothing.

Reference solution

Python

from typing import List

def divideArray(nums: List[int], k: int) -> List[List[int]]:
    s = sorted(nums)
    out = []
    for i in range(0, len(s), 3):
        if s[i + 2] - s[i] > k:
            return []
        out.append([s[i], s[i + 1], s[i + 2]])
    return out

JavaScript

var divideArray = function(nums, k) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var out = [];
    for (var i = 0; i < s.length; i += 3) {
        if (s[i + 2] - s[i] > k) return [];
        out.push([s[i], s[i + 1], s[i + 2]]);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue