Problem Statement
My solution
class Solution:
def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
N = len(nums)
res = [0] * N
idx = 0
for num in nums:
if num < pivot:
res[idx] = num
idx += 1
for num in nums:
if num == pivot:
res[idx] = num
idx += 1
for num in nums:
if num > pivot:
res[idx] = num
idx += 1
return res
Editorial
Approach 1: Dynamic Lists
class Solution:
def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
less = []
equal = []
greater = []
for num in nums:
if num < pivot:
less.append(num)
elif num > pivot:
greater.append(num)
else:
equal.append(num)
less.extend(equal)
less.extend(greater)
return less
Approach 2: Two Passes With Fixed Array
class Solution:
def pivotArray(self, nums, pivot):
less = 0
equal = 0
for num in nums:
if num < pivot:
less += 1
elif num == pivot:
equal += 1
ans = [0] * len(nums)
lessI = 0
equalI = less
greaterI = less + equal
for i in range(len(nums)):
num = nums[i]
if num < pivot:
ans[lessI] = num
lessI += 1
elif num > pivot:
ans[greaterI] = num
greaterI += 1
else:
ans[equalI] = num
equalI += 1
return ans
Approach 3: Two Pointer
class Solution:
def pivotArray(self, nums, pivot):
ans = [0] * len(nums)
less_i = 0
greater_i = len(nums) - 1
for i, j in zip(range(len(nums)), range(len(nums) - 1, -1, -1)):
if nums[i] < pivot:
ans[less_i] = nums[i]
less_i += 1
if nums[j] > pivot:
ans[greater_i] = nums[j]
greater_i -= 1
while less_i <= greater_i:
ans[less_i] = pivot
less_i += 1
return ans
