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

Partition Array According to Given Pivot

Number: 2265

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Google, Apple

Problem Description

Given an array of integers and a pivot value, rearrange the array so that all elements less than the pivot appear first, followed by elements equal to the pivot, and then elements greater than the pivot. The relative order of the elements less than or greater than the pivot must be maintained.

Key Insights

  • Use three separate lists/arrays for elements less than, equal to, and greater than the pivot.
  • Traverse the input array once to distribute elements into the respective lists.
  • Concatenate the lists in order: less-than, equal-to, and greater-than.
  • Maintain order preservation by appending elements in the order they are encountered.

Space and Time Complexity

Time Complexity: O(n), where n is the number of elements in the array. Space Complexity: O(n), due to the temporary storage for three sub-arrays.

Solution

The solution uses a simulation approach by making a single pass through the input array and partitioning the elements into three separate lists: one for values less than the pivot, one for values equal to the pivot, and one for values greater than the pivot. This preserves the original relative order of the elements. Finally, the three lists are concatenated into the final result.

Code Solutions

# Function to partition the array according to the given pivot
def pivotArray(nums, pivot):
    # Lists to store different categories of elements
    less_than = []   # Elements less than pivot
    equal_to = []    # Elements equal to pivot
    greater_than = []  # Elements greater than pivot

    # Iterate over each element in the array
    for num in nums:
        if num < pivot:
            less_than.append(num)  # Append if element is less than pivot
        elif num == pivot:
            equal_to.append(num)   # Append if element is equal to pivot
        else:
            greater_than.append(num)  # Append if element is greater than pivot

    # Concatenate the three lists in the required order and return
    return less_than + equal_to + greater_than

# Example usage
nums_example = [9,12,5,10,14,3,10]
pivot_value = 10
print(pivotArray(nums_example, pivot_value))
← Back to All Questions