aboutsummaryrefslogtreecommitdiff
path: root/partition_arr_pivot.py
blob: 7c8a305f8ba027f7bc884f926034556f4122d6b1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# 2161. Partition Array According to Given Pivot

"""
you are given a 0-indexed integer array 'nums' and an integer 'pivot'.
rearrange 'nums' such that the following conditions are satisfied: every
element less than 'pivot' appears befor every element greater than 'pivot',
every element equal to 'pivot' appears in between the elements less than and
greater than 'pivot', the relative order of the elments less than 'pivot' and
the elements greater than 'pivot' is maintained. return 'nums' after the
rearrangement
"""


class Solution(object):
    def pivotArray(self, nums, pivot):
        """
        :type nums: List[int]
        :type pivot: int
        :rtype: List[int]
        """
        ans = [0] * len(nums)
        left, right = 0, len(nums) - 1
        for i, j in zip(range(len(nums)), range(len(nums) - 1, -1, -1)):
            if nums[i] < pivot:
                ans[left] = nums[i]
                left += 1
            if nums[j] > pivot:
                ans[right] = nums[j]
                right -= 1
        while left <= right:
            ans[left] = pivot
            left += 1
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.pivotArray(nums=[9, 12, 5, 10, 14, 3, 10], pivot=10))
    print(obj.pivotArray(nums=[-3, 4, 3, 2], pivot=2))