Divide Array Into Arrays With Max Difference

Divide Array Into Arrays With Max Difference - Problem

You are given an integer array nums of size n where n is a multiple of 3 and a positive integer k.

Divide the array nums into n / 3 arrays of size 3 satisfying the following condition:

The difference between any two elements in one array is less than or equal to k.

Return a 2D array containing the arrays. If it is impossible to satisfy the conditions, return an empty array. And if there are multiple answers, return any of them.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,3,5,2,4,6], k = 2

› Output: [[1,2,3],[4,5,6]]

💡 Note: After sorting: [1,2,3,4,5,6]. Group consecutively: [1,2,3] has max diff 3-1=2≤k, [4,5,6] has max diff 6-4=2≤k.

Example 2 — Impossible Case

$ Input: nums = [1,3,3,2,7,3], k = 3

› Output: []

💡 Note: After sorting: [1,2,3,3,3,7]. First group [1,2,3] works (diff=2≤3), but second group [3,3,7] has diff=4>3, so return empty array.

Example 3 — All Same Elements

$ Input: nums = [2,2,2,2,2,2], k = 0

› Output: [[2,2,2],[2,2,2]]

💡 Note: All elements are identical, so max difference in any group is 0≤k=0. Any grouping works.

Constraints

n == nums.length
1 ≤ n ≤ 10⁵
n is a multiple of 3
1 ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Original array with n elements (multiple of 3) and constraint k

Sort & Group

Sort array and form consecutive triplets

Validate & Return

Check each group's max difference ≤ k, return result

Key Takeaway

🎯 Key Insight: Sorting first ensures that consecutive grouping minimizes differences within each group

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Facebook 12

The key insight is that sorting first enables optimal grouping. By arranging elements in ascending order, we can greedily form consecutive triplets that minimize internal differences. Best approach is Sort + Greedy: Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Greedy Grouping	O(n log n)	O(1)	Sort array first, then greedily form consecutive groups of 3
Try All Combinations	O(n!)	O(n)	Generate all possible ways to divide array into groups of 3

Sort and Greedy Grouping — Algorithm Steps

Sort the array in ascending order
Take consecutive triplets from sorted array
Check if each triplet satisfies max difference ≤ k
Return all triplets if valid, empty array otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Array

Arrange elements in ascending order

Group Consecutively

Take groups of 3 consecutive elements

Validate

Check if max - min ≤ k for each group

Code -

solution.c — C

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

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

int** solution(int* nums, int numsSize, int k, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if (numsSize % 3 != 0) return NULL;
    
    // Sort the array
    qsort(nums, numsSize, sizeof(int), compare);
    
    int groupCount = numsSize / 3;
    int** result = (int**)malloc(groupCount * sizeof(int*));
    *returnColumnSizes = (int*)malloc(groupCount * sizeof(int));
    
    // Take consecutive triplets
    for (int i = 0; i < numsSize; i += 3) {
        // Check if max difference <= k
        if (nums[i+2] - nums[i] > k) {
            free(result);
            free(*returnColumnSizes);
            *returnSize = 0;
            return NULL;  // Invalid grouping
        }
        
        result[*returnSize] = (int*)malloc(3 * sizeof(int));
        result[*returnSize][0] = nums[i];
        result[*returnSize][1] = nums[i+1];
        result[*returnSize][2] = nums[i+2];
        (*returnColumnSizes)[*returnSize] = 3;
        (*returnSize)++;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int k;
    scanf("%d", &k);
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(nums, numsSize, k, &returnSize, &returnColumnSizes);
    
    if (result == NULL || returnSize == 0) {
        printf("[]\n");
    } else {
        printf("[");
        for (int i = 0; i < returnSize; i++) {
            if (i > 0) printf(",");
            printf("[");
            for (int j = 0; j < returnColumnSizes[i]; j++) {
                if (j > 0) printf(",");
                printf("%d", result[i][j]);
            }
            printf("]");
        }
        printf("]\n");
    }
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), grouping takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort and Greedy Grouping — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler