Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #User function template for Python
- class Solution:
- #Function to partition the array around the range such
- #that array is divided into three parts.
- def threeWayPartition(self, arr, a, b):
- # code here
- l=0
- r=len(arr)-1
- m=0
- '''
- l: before l all elements <a
- r:after r all elements >b.
- Actually whenevet we find arr[m]<a
- we directly exchange with arr[l] and
- increment both.
- But in the case of arr[m]>b
- even though after exchanging
- arr[m] and arr[r] we shouldnot
- increment m (we can decrement r).
- Because the place at arr[m] after
- exchanging might be a value <a.
- so we have to stay at m and
- shouldnt increment m immediately
- please check sorting colors video
- neetcode video.
- '''
- while m<=r:#VV imp m and r should not cross
- if arr[m]<a:
- arr[l],arr[m]=arr[m],arr[l]
- l=l+1
- elif arr[m]>b:
- arr[r],arr[m]=arr[m],arr[r]
- m=m-1
- r=r-1
- m=m+1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement