Skip to main content
Talentd

Distribute Elements Into Two Arrays I - Solution & Explanation

EasyArraySimulation15 min readAsked at: Amazon, Autodesk
Practice this problem

Problem Statement

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.

Approach Overview

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 1: Approach 1: Using Hash Maps

This approach leverages hash maps (or dictionaries) to store and retrieve elements quickly. The idea is to traverse the data structure and keep track of elements, which allows for efficient lookups and updates. This can help solve problems like finding duplicates, counting frequencies, or intersection of elements.

This C solution uses a simple array to simulate a hash map for storing the frequency of occurrences of elements. It initializes the mapping array, counts frequencies, and then collects elements which have duplicates. The final array contains all duplicate elements.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + k), where n is the number of elements, and k is the size of the array used as hash map.
Space Complexity: O(k), where k is the size needed for the hash map.

Try this approach in the editor →

Approach 2: Approach 2: In-place Marking

This method involves manipulating the input data structure to keep track of visited elements. It's usually employed when the modification of input is allowed, and we can utilize specific properties of the elements, like their range.

This C solution marks visiting elements by negating the value at the index corresponding to the value of the current element. If an index is found already negative during a visit, the element is a duplicate.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(1), since we are not using extra space aside from the result array.

Try this approach in the editor →

Approach 3: Simulation

We create two arrays arr1 and arr2 to store the elements of nums. Initially, arr1 contains only nums[0], and arr2 contains only nums[1].

Then we iterate over the elements of nums starting from index 2. If the last element of arr1 is greater than the last element of arr2, we append the current element to arr1; otherwise, we append it to arr2.

Finally, we append the elements of arr2 to arr1 and return arr1.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using Hash Maps

Time Complexity: O(n + k), where n is the number of elements, and k is the size of the array used as hash map.
Space Complexity: O(k), where k is the size needed for the hash map.

Approach 2: In-place Marking

Time Complexity: O(n), where n is the number of elements.
Space Complexity: O(1), since we are not using extra space aside from the result array.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Hash Map TrackingO(n)O(n)Clear and readable implementation when building arrays dynamically
In-place MarkingO(n)O(1)Memory constrained scenarios or when minimizing auxiliary storage

Video Solution

100243 Distribute Elements Into Two Arrays I | leetcode | contest 387 | solved | java | solved • Ssquare • 1,017 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Distribute Elements Into Two Arrays I easy or hard?
Distribute Elements Into Two Arrays I is classified as an Easy problem. The main challenge is correctly following the rule that compares the last elements of the two arrays. Once the simulation logic is implemented, the algorithm runs in linear time with straightforward code.
Distribute Elements Into Two Arrays I Python/Java solution
In Python or Java, create two lists or ArrayLists and initialize them with the first two elements. Iterate through the rest of nums, compare the last values using arr1[-1] and arr2[-1] (or get(size-1) in Java), append the element to the appropriate list, and finally merge the lists into the output array.
How to solve Distribute Elements Into Two Arrays I in O(n)?
Start arr1 with nums[0] and arr2 with nums[1]. Traverse the array from index 2 onward. Compare the last element of arr1 and arr2; append the current number to arr1 if its last value is larger, otherwise append it to arr2. After finishing the traversal, return the concatenation of arr1 followed by arr2.
What is the best approach for Distribute Elements Into Two Arrays I?
The best approach is a direct simulation using two arrays and comparing their last elements at each step. Iterate through the input once, append the current element to arr1 or arr2 depending on which array has the larger last value, and finally concatenate both arrays. This solution runs in O(n) time and uses O(n) space for the resulting arrays.
Is Distribute Elements Into Two Arrays I asked at Google/Amazon/Meta?
Problems of this style appear frequently in screening rounds at companies like Amazon and Google because they test basic array manipulation and careful implementation of rules. While this exact problem may not always appear, similar simulation and array distribution tasks are common in interviews.
What data structure is used in Distribute Elements Into Two Arrays I?
The primary data structure is a dynamic array or list to store arr1 and arr2 as elements are appended. Some implementations also use a small hash map to track the latest values of each array, but the core idea relies on simple array operations and comparisons.
What is the time complexity of Distribute Elements Into Two Arrays I?
The time complexity is O(n) because each element in the input array is processed exactly once. Every step performs a constant-time comparison and append operation. The space complexity is O(n) since two arrays are built to store the distributed elements.

Ready to solve this problem?

Practice Distribute Elements Into Two Arrays I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Divide Array Into Equal Pairs

Next

Split Array Largest Sum