# Distribute Elements Into Two Arrays I
**Difficulty:** EASY
[External](https://leetcode.com/problems/distribute-elements-into-two-arrays-i)
Canonical: https://scaleengineer.com/dsa/problems/distribute-elements-into-two-arrays-i
**Data structures:** Array
**Companies:** [Autodesk](https://scaleengineer.com/companies/autodesk)
---
## Problem
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
## Simulation with Manual Array Resizing
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Efficient Simulation with Dynamic Arrays
This is the optimal approach, which simulates the process using dynamic arrays (like Java's `ArrayList`). Dynamic arrays provide amortized O(1) time complexity for adding elements to the end, making the overall simulation linear in time.
**Time:** O(n), where `n` is the number of elements in `nums`. The main loop runs `n-2` times, with each operation inside being O(1) amortized. The final concatenation is O(n). · **Space:** O(n). The two `ArrayLists` require O(n) auxiliary space to store the numbers. The output array also takes O(n) space.
**Pros:** Optimal time complexity for the problem.; Clean, readable, and idiomatic code using standard library features.
**Cons:** Uses slightly more memory than primitive arrays due to object wrappers and `ArrayList` overhead, though this is negligible.
### Explanation
This is the optimal approach, which simulates the process using dynamic arrays (like Java's `ArrayList`). Dynamic arrays provide amortized O(1) time complexity for adding elements to the end, making the overall simulation linear in time.

The algorithm is as follows:
*   Initialize two empty `ArrayLists`, `arr1` and `arr2`.
*   Add `nums[0]` to `arr1` and `nums[1]` to `arr2`.
*   Iterate through `nums` from index `i = 2`.
*   In each step, get the last elements of `arr1` and `arr2` (an O(1) operation).
*   If `arr1`'s last element is greater, add `nums[i]` to `arr1`.
*   Otherwise, add `nums[i]` to `arr2`. Adding to the end is an amortized O(1) operation.
*   After the loop, create a new integer array `result`.
*   Copy elements from `arr1` and then `arr2` into the `result` array.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] resultArray(int[] nums) {
        List<Integer> arr1 = new ArrayList<>();
        List<Integer> arr2 = new ArrayList<>();

        arr1.add(nums[0]);
        arr2.add(nums[1]);

        for (int i = 2; i < nums.length; i++) {
            if (arr1.get(arr1.size() - 1) > arr2.get(arr2.size() - 1)) {
                arr1.add(nums[i]);
            } else {
                arr2.add(nums[i]);
            }
        }

        int[] result = new int[nums.length];
        int index = 0;
        for (int num : arr1) {
            result[index++] = num;
        }
        for (int num : arr2) {
            result[index++] = num;
        }

        return result;
    }
}
```
### Algorithm
*   Initialize two dynamic arrays, `arr1` and `arr2` (e.g., `ArrayList` in Java).
*   Add `nums[0]` to `arr1` and `nums[1]` to `arr2`.
*   Iterate through `nums` from index `i = 2`.
*   Get the last elements of `arr1` and `arr2` in O(1) time.
*   Compare the last elements and add `nums[i]` to the appropriate list. This append operation is amortized O(1).
*   After the loop, create a new primitive array `result` of size `n`.
*   Copy the elements from `arr1` followed by `arr2` into `result`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> resultArray(vector<int> &nums) {
    int n = nums.size();
    vector<int> arr1 = {nums[0]};
    vector<int> arr2 = {nums[1]};
    for (int k = 2; k < n; ++k) {
      if (arr1.back() > arr2.back()) {
        arr1.push_back(nums[k]);
      } else {
        arr2.push_back(nums[k]);
      }
    }
    arr1.insert(arr1.end(), arr2.begin(), arr2.end());
    return arr1;
  }
};

```

### Python

```python
class Solution:
    def resultArray(self, nums: List[int]) -> List[int]: arr1 = [nums[0]] arr2 = [nums[1]] for x in nums[2:]: if arr1[- 1] > arr2[- 1]: arr1 . append(x) else: arr2 . append(x) return arr1 + arr2

```