We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Distribute Elements Into Two Arrays I

Number: 3347

Difficulty: Easy

Paid? No

Companies: Autodesk

Problem Description

Given a 1-indexed array of distinct integers, distribute the elements into two arrays, arr1 and arr2, through n operations. Initially, add the first element to arr1 and the second element to arr2. For each subsequent element, compare the last elements of arr1 and arr2; if the last element of arr1 is greater than that of arr2, append the element to arr1, otherwise append it to arr2. Finally, return the result obtained by concatenating arr1 and arr2.

Key Insights

  • The problem requires simulating the operations as described.
  • Each operation depends solely on the current state (last elements) of arr1 and arr2.
  • The constraints are small (n up to 50), allowing a straightforward solution with linear iteration.
  • Use simple dynamic arrays (lists) for storing elements.

Space and Time Complexity

Time Complexity: O(n) - We perform a single pass through the input array. Space Complexity: O(n) - We use additional arrays to store the distributed elements.

Solution

We solve the problem by simulating the operations according to the rules provided. Start by initializing arr1 with the first element and arr2 with the second element. Then for each subsequent number, check the last element in arr1 and arr2. Append the number to arr1 if its last element is greater than that of arr2; otherwise, append it to arr2. Finally, merge arr1 and arr2 to form the resulting array. The approach is intuitive and leverages conditional checks along with dynamic array updates.

Code Solutions

# Python solution

def distribute_elements(nums):
    # Initialize arr1 with the first element and arr2 with the second element.
    arr1 = [nums[0]]
    arr2 = [nums[1]]
    
    # Process the remaining elements starting at the third element.
    for num in nums[2:]:
        # If the last element of arr1 is greater than the last element of arr2,
        # then append num to arr1; otherwise, append to arr2.
        if arr1[-1] > arr2[-1]:
            arr1.append(num)
        else:
            arr2.append(num)
    
    # Return the concatenation of arr1 and arr2.
    return arr1 + arr2

# Example Usage:
# nums = [2,1,3]
# print(distribute_elements(nums))  # Output: [2,3,1]
← Back to All Questions