Scale Engineer

Distribute Elements Into Two Arrays I

Easy
#2725Time: O(n^2), where `n` is the number of elements in `nums`. Each addition to an array can take up to O(n) time for copying, and this is done O(n) times.Space: O(n). The space for `arr1` and `arr2` sums to O(n). Temporary arrays for resizing also contribute, but the peak space remains O(n).1 company
Data structures
Array
Companies
Autodesk

Prompt

You are given a 1-indexed array of distinct integers nums of length n.

You need to distribute all the elements of nums between two arrays arr1 and arr2 using n operations. In the first operation, append nums[1] to arr1. In the second operation, append nums[2] to arr2. Afterwards, in the ith operation:

  • If the last element of arr1 is greater than the last element of arr2, append nums[i] to arr1. Otherwise, append nums[i] to arr2.

The array result is formed by concatenating the arrays arr1 and arr2. For example, if arr1 == [1,2,3] and arr2 == [4,5,6], then result = [1,2,3,4,5,6].

Return the array result.

 

Example 1:

Input: nums = [2,1,3]
Output: [2,3,1]
Explanation: After the first 2 operations, arr1 = [2] and arr2 = [1].
In the 3rd operation, as the last element of arr1 is greater than the last element of arr2 (2 > 1), append nums[3] to arr1.
After 3 operations, arr1 = [2,3] and arr2 = [1].
Hence, the array result formed by concatenation is [2,3,1].

Example 2:

Input: nums = [5,4,3,8]
Output: [5,3,4,8]
Explanation: After the first 2 operations, arr1 = [5] and arr2 = [4].
In the 3rd operation, as the last element of arr1 is greater than the last element of arr2 (5 > 4), append nums[3] to arr1, hence arr1 becomes [5,3].
In the 4th operation, as the last element of arr2 is greater than the last element of arr1 (4 > 3), append nums[4] to arr2, hence arr2 becomes [4,8].
After 4 operations, arr1 = [5,3] and arr2 = [4,8].
Hence, the array result formed by concatenation is [5,3,4,8].

 

Constraints:

  • 3 <= n <= 50
  • 1 <= nums[i] <= 100
  • All elements in nums are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the distribution process using basic arrays. For each new element to be added to arr1 or arr2, a new, larger array is created, and all existing elements are copied over along with the new element. This manual resizing is computationally expensive.

Algorithm

  • Initialize arr1 with nums[0] and arr2 with nums[1] using primitive arrays.
  • Iterate through nums from index i = 2.
  • Compare arr1[arr1.length - 1] and arr2[arr2.length - 1].
  • Based on the comparison, create a new array one size larger than the target array (arr1 or arr2).
  • Copy the elements from the old array to the new one.
  • Add nums[i] to the end of the new array.
  • Replace the old array reference with the new one.
  • After the loop, concatenate arr1 and arr2 to form the result.

Walkthrough

This approach directly simulates the distribution process using basic arrays. For each new element to be added to arr1 or arr2, a new, larger array is created, and all existing elements are copied over along with the new element. This manual resizing is computationally expensive.

The algorithm proceeds as follows:

  • Initialize arr1 as a new array containing just nums[0].
  • Initialize arr2 as a new array containing just nums[1].
  • Iterate from i = 2 to n-1.
  • In each step, compare the last element of arr1 and arr2.
  • If arr1's last element is greater, create a new array for arr1 that is one element larger, copy the old elements, and add nums[i] at the end.
  • Otherwise, do the same for arr2.
  • After the loop, concatenate arr1 and arr2 into a final result array.
import java.util.Arrays; class Solution {    public int[] resultArray(int[] nums) {        if (nums.length <= 2) {            return nums;        }         int[] arr1 = new int[]{nums[0]};        int[] arr2 = new int[]{nums[1]};         for (int i = 2; i < nums.length; i++) {            if (arr1[arr1.length - 1] > arr2[arr2.length - 1]) {                int[] newArr1 = new int[arr1.length + 1];                System.arraycopy(arr1, 0, newArr1, 0, arr1.length);                newArr1[arr1.length] = nums[i];                arr1 = newArr1;            } else {                int[] newArr2 = new int[arr2.length + 1];                System.arraycopy(arr2, 0, newArr2, 0, arr2.length);                newArr2[arr2.length] = nums[i];                arr2 = newArr2;            }        }         int[] result = new int[nums.length];        System.arraycopy(arr1, 0, result, 0, arr1.length);        System.arraycopy(arr2, 0, result, arr1.length, arr2.length);        return result;    }}

Complexity

Time

O(n^2), where `n` is the number of elements in `nums`. Each addition to an array can take up to O(n) time for copying, and this is done O(n) times.

Space

O(n). The space for `arr1` and `arr2` sums to O(n). Temporary arrays for resizing also contribute, but the peak space remains O(n).

Trade-offs

Pros

  • It's a straightforward implementation that uses only basic arrays.

  • The logic directly maps to the problem description.

Cons

  • Very inefficient due to O(n) cost for each element addition.

  • Not suitable for larger inputs beyond the given constraints.

Solutions

class Solution {public  int[] resultArray(int[] nums) {    int n = nums.length;    int[] arr1 = new int[n];    int[] arr2 = new int[n];    arr1[0] = nums[0];    arr2[0] = nums[1];    int i = 0, j = 0;    for (int k = 2; k < n; ++k) {      if (arr1[i] > arr2[j]) {        arr1[++i] = nums[k];      } else {        arr2[++j] = nums[k];      }    }    for (int k = 0; k <= j; ++k) {      arr1[++i] = arr2[k];    }    return arr1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem