Watch 10 video solutions for Distribute Elements Into Two Arrays I, a easy level problem involving Array, Simulation. This walkthrough by Ayush Rao has 509 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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 <= 501 <= nums[i] <= 100nums are distinct.Problem Overview: You are given an integer array nums. Start two arrays: arr1 with nums[0] and arr2 with nums[1]. For every remaining element, compare the last elements of both arrays. If the last value in arr1 is greater than the last value in arr2, append the current number to arr1; otherwise append it to arr2. After processing all elements, return the concatenation of arr1 followed by arr2. The task is essentially a controlled array construction problem using simple simulation.
Approach 1: Using Hash Maps (O(n) time, O(n) space)
Track the last value of each constructed array using a small hash map keyed by array index (1 for arr1, 2 for arr2). Iterate through nums starting from index 2. On each step, read the stored last values, compare them, and append the current element to the appropriate array. Update the map entry to reflect the new last value. Hash lookups are constant time, so each iteration performs only a few comparisons and updates. This approach keeps the logic explicit and easy to follow, which is useful when extending the rule set or debugging the distribution process.
Approach 2: In-place Marking (O(n) time, O(1) extra space)
Instead of storing extra structures, reuse the input array to mark which target array each element belongs to. Maintain two variables holding the latest values of arr1 and arr2. During a single pass through nums, compare these values and mark the current index accordingly (for example, with a small flag array or encoded value). After the pass, perform a second traversal to build the final result by first collecting elements assigned to arr1 and then those assigned to arr2. The comparison logic stays the same, but auxiliary memory is minimized.
Recommended for interviews: The straightforward simulation approach (tracking the last elements and appending during iteration) is what most interviewers expect. It demonstrates that you correctly interpret the rule and implement efficient array operations in O(n) time. Showing awareness of a space-optimized variation, such as in-place marking, signals deeper understanding of memory tradeoffs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map Tracking | O(n) | O(n) | Clear and readable implementation when building arrays dynamically |
| In-place Marking | O(n) | O(1) | Memory constrained scenarios or when minimizing auxiliary storage |