How do you solve Partition Array According to Given Pivot on LeetCode?

Partition Array According to Given Pivot (LeetCode #2161) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using two pointers can significantly reduce the time complexity from O(n²) to O(n).

What is the brute force solution for Partition Array According to Given Pivot?

The brute force approach for Partition Array According to Given Pivot is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute-force approach involves creating separate lists for elements less than, equal to, and greater than the pivot. Then, we concatenate these lists to form the final result. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Partition Array According to Given Pivot?

Partition Array According to Given Pivot uses the following concepts: Array, Two Pointers, Simulation. The recommended patterns to study are: Two Pointers, Array.

What are the interview tips for Partition Array According to Given Pivot?

Always consider edge cases, such as when all elements are the same as the pivot. Explain your thought process clearly while coding; it shows your understanding. Practice the two-pointer technique, as it's commonly used in interview problems.

What are common mistakes when solving Partition Array According to Given Pivot?

Not maintaining the relative order of elements when rearranging. Using extra space unnecessarily when a two-pointer technique could be applied.

#2161

Partition Array According to Given Pivot

Medium

ArrayTwo PointersSimulationTwo PointersArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses a two-pointer technique to rearrange the elements in a single pass. This is more efficient as it avoids the need for additional lists and maintains the relative order.

⚙️

Algorithm

3 steps

1Step 1: Initialize two pointers: left for the start and right for the end of the array.
2Step 2: Use a while loop to iterate until left pointer crosses right pointer.
3Step 3: If the element at the left pointer is less than pivot, move it to the front. If it's equal, just move the left pointer. If it's greater, swap it with the element at the right pointer and decrement the right pointer.

solution.py11 lines

1def pivotArray(nums, pivot):
2    left, right = 0, len(nums) - 1
3    while left <= right:
4        if nums[left] < pivot:
5            left += 1
6        elif nums[left] > pivot:
7            nums[left], nums[right] = nums[right], nums[left]
8            right -= 1
9        else:
10            left += 1
11    return nums

ℹ

Complexity note: The time complexity is O(n) because we traverse the array once. The space complexity is O(1) since we are rearranging the elements in place without using extra space.

1Using two pointers can significantly reduce the time complexity from O(n²) to O(n).
2Maintaining the relative order of elements is crucial for this problem.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.