3069. Distribute Elements Into Two Arrays I

3069. Distribute Elements Into Two Arrays I

Difficulty: Easy

Topics: Mid Level, Array, Simulation, Weekly Contest 387

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. Afterward, in the iᵗʰ 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 3ʳᵈ 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 3ʳᵈ 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 4ᵗʰ 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].

Example 3:

• Input: nums = [1,3,2,4]
• Output: [1,3,2,4]

Example 4:

• Input: nums = [4,3,2,1]
• Output: [4,2,3,1]

Example 5:

• Input: nums = [10,5,7]
• Output: [10,7,5]

Example 6:

• Input: nums = [100,1,99,2,98,3]
• Output: [100,99,2,98,3,1]

Constraints:

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

Hint:

1. Divide the array into two arrays by keeping track of the last elements of both subarrays.

Solution:

We implemented an efficient solution that distributes elements from a given 1-indexed integer array into two separate arrays based on a simple comparison rule, then concatenates them to return the final result. The approach simulates the process step-by-step while maintaining only the last elements of each array for decision-making, ensuring clarity and optimal performance.

Approach

• Initialize arr1 with nums[0] and arr2 with nums[1] (0-indexed).
• Loop through the remaining elements starting from index 2 up to n-1.
• At each step, compare the last element of arr1 and the last element of arr2.
• If the last element of arr1 is greater than the last element of arr2, append the current nums[i] to arr1. Otherwise, append it to arr2.
• After processing all elements, concatenate arr1 and arr2 using array_merge() and return the result.

Let's implement this solution in PHP: 3069. Distribute Elements Into Two Arrays I

<?php
/**
 * @param Integer[] $nums
 * @return Integer[]
 */
function resultArray(array $nums): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo resultArray([2,1,3]) .  "\n";                  // Output: [2,3,1]
echo resultArray([5,4,3,8]) .  "\n";                // Output: [5,3,4,8]
echo resultArray([1,2,3,4]) .  "\n";                // Output: [1,3,2,4]
echo resultArray([4,3,2,1]) .  "\n";                // Output: [4,2,3,1]
echo resultArray([10,5,7]) .  "\n";                 // Output: [10,7,5]
echo resultArray([100,1,99,2,98,3]) .  "\n";        // Output: [100,99,2,98,3,1]
?>

Explanation:

• Initial setup: The first two elements are placed into arr1 and arr2 respectively, as per the problem statement.
• Iterative distribution: For each subsequent element, we check the last elements of both arrays. The comparison determines which array receives the new element.
• Efficient tracking: Since only the last element of each array influences the decision, we only need to keep track of the most recently added value, making the logic straightforward.
• Final concatenation: After the distribution loop, the two arrays are merged in order (arr1 first, then arr2) to form the required result array.

Complexity Analysis

• Time Complexity: O(n) — We iterate through the array once, performing constant-time operations for each element.
• Space Complexity: O(n) — We store the elements in two separate arrays, which together hold all n elements of the input.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub