Divide Array Into Arrays With Max Difference

Medium
605.

Divide Array Into Arrays With Max Difference

Divide Array Into Arrays With Max Difference is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[][]}
 */
var divideArray = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Divide Array Into Arrays With Max Difference — Solution

Divide Array Into Arrays With Max Difference solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Divide Array Into Arrays With Max Difference is a medium coding problem on arrays, sorting and greedy, asked in Amazon and Flipkart interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy
  • 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

Hints for Divide Array Into Arrays With Max Difference

  1. Hint 1

    Sort first. Once sorted, the span of a group is its last element minus its first.

  2. Hint 2

    Adjacent triples in sorted order are the best possible grouping — pulling elements apart can only widen some group.

  3. Hint 3

    Check s[i+2] - s[i] <= k for each triple; one failure kills the whole split.

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

Java

public static int[][] divideArray(int[] nums, int k) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int groups = s.length / 3;
    int[][] out = new int[groups][3];
    for (int i = 0, g = 0; i < s.length; i += 3, g++) {
        if (s[i + 2] - s[i] > k) return new int[0][];
        out[g][0] = s[i];
        out[g][1] = s[i + 1];
        out[g][2] = s[i + 2];
    }
    return out;
}

C++

vector<vector<int>> divideArray(vector<int>& nums, int k) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    vector<vector<int>> out;
    for (size_t i = 0; i < s.size(); i += 3) {
        if (s[i + 2] - s[i] > k) return {};
        out.push_back({ 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms