Advertisement
Iam_Sandeep

Three way partitioning of array around a given value dutch national flag varient

Jun 17th, 2022 (edited)
1,051
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.16 KB | None | 0 0
  1. #User function template for Python
  2.  
  3. class Solution:
  4.     #Function to partition the array around the range such
  5.     #that array is divided into three parts.
  6.     def threeWayPartition(self, arr, a, b):
  7.         # code here
  8.         l=0
  9.         r=len(arr)-1
  10.         m=0
  11.         '''
  12.        l: before l all elements <a
  13.        r:after r all elements >b.
  14.        Actually whenevet we find arr[m]<a
  15.        we directly exchange with arr[l] and
  16.        increment both.
  17.        But in the case of arr[m]>b
  18.        even though after exchanging
  19.        arr[m] and arr[r] we shouldnot
  20.        increment m (we can decrement r).
  21.        Because the place at arr[m] after
  22.        exchanging might be a value <a.
  23.        so we have to stay at m and
  24.        shouldnt increment m immediately
  25.         please check sorting colors video
  26.         neetcode video.
  27.        '''
  28.        
  29.         while m<=r:#VV imp m and r should not cross
  30.             if arr[m]<a:
  31.                 arr[l],arr[m]=arr[m],arr[l]
  32.                 l=l+1
  33.             elif arr[m]>b:
  34.                 arr[r],arr[m]=arr[m],arr[r]
  35.                 m=m-1
  36.                 r=r-1
  37.             m=m+1
  38.  
  39.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement