Divide array into arrays with max difference

Array Greedy Sorting

79.0% acceptance

Feb 25, 2026

1165

222

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn divide_array(mut nums: Vec<i32>, k: i32) -> Vec<Vec<i32>> {
    nums.sort_unstable();
    let n = nums.len();
    let mut result = Vec::new();
    for i in (0..n).step_by(3) {
      if nums[i + 2] - nums[i] > k {
        return vec![];
      }
      result.push(vec![nums[i], nums[i + 1], nums[i + 2]]);
    }
    result
  }
}