Given an array of size n and a range [a, b]. The task is to partition the array around the range such that array is divided into three parts.
1) All elements smaller than a come first.
2) All elements in range a to b come next.
3) All elements greater than b appear in the end.
The individual elements of three sets can appear in any order. You are required to return the modified array.
Note: The generated output is 1 if you modify the given array successfully.
Example 1:
Input: 
n = 5
A[] = {1, 2, 3, 3, 4}
[a, b] = [1, 2]
Output: 1
Explanation: One possible arrangement is:
{1, 2, 3, 3, 4}. If you return a valid
arrangement, output will be 1.
Example 2:
Input: 
n = 3 
A[] = {1, 2, 3}
[a, b] = [1, 3]
Output: 1
Explanation: One possible arrangement 
is: {1, 2, 3}. If you return a valid
arrangement, output will be 1.
Your Task: 
You don't need to read input or print anything. The task is to complete the function threeWayPartition() which takes the array[], a, and b as input parameters and modifies the array in-place according to the given conditions.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 <= n <= 10^{6}
1 <= A[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #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, array, a, b):

	    # code here 

Solutions:
class Solution:

	def threeWayPartition(self, array, a, b):
		(st, end, i) = (0, len(array) - 1, 0)
		while i <= end:
			if array[i] < a:
				(array[i], array[st]) = (array[st], array[i])
				st += 1
			elif array[i] > b:
				(array[i], array[end]) = (array[end], array[i])
				end -= 1
				i -= 1
			i += 1


class Solution:

	def threeWayPartition(self, array, a, b):
		p1 = []
		p2 = []
		p3 = []
		for i in array:
			if i < a:
				p1.append(i)
			elif i <= b:
				p2.append(i)
			else:
				p3.append(i)
		p = p1 + p2 + p3
		for i in range(len(array)):
			array[i] = p[i]


class Solution:

	def threeWayPartition(self, array, a, b):
		l = [i for i in array if i < a]
		k = [i for i in array if i >= a and i <= b]
		n = [i for i in array if i > b]
		array.clear()
		array = l[:] + k[:] + n[:]


class Solution:

	def threeWayPartition(self, arr, a, b):
		n = len(arr) - 1
		(i, j) = (0, n)
		while i < j:
			if arr[i] < a:
				i += 1
			elif arr[j] >= a:
				j -= 1
			elif arr[i] >= a and arr[j] < a:
				tmp = arr[j]
				arr[j] = arr[i]
				arr[i] = tmp
		j = n
		while i < j:
			if arr[i] <= b:
				i += 1
			elif arr[j] > b:
				j -= 1
			elif arr[i] > b and arr[j] <= b:
				tmp = arr[j]
				arr[j] = arr[i]
				arr[i] = tmp


class Solution:

	def threeWayPartition(self, array, a, b):
		smaller = []
		ranger = []
		greater = []
		for i in array:
			if i < a:
				smaller.append(i)
			if i > b:
				greater.append(i)
			if i >= a and i <= b:
				ranger.append(i)
		c = 0
		for i in smaller:
			array[c] = i
			c += 1
		for i in ranger:
			array[c] = i
			c += 1
		for i in greater:
			array[c] = i
			c += 1


class Solution:

	def threeWayPartition(self, array, a, b):
		(low, mid) = (0, 0)
		high = len(array) - 1
		while mid <= high:
			if array[mid] < a:
				(array[mid], array[low]) = (array[low], array[mid])
				mid += 1
				low += 1
			elif array[mid] >= a and array[mid] <= b:
				mid += 1
			else:
				(array[mid], array[high]) = (array[high], array[mid])
				high -= 1
		return array


class Solution:

	def threeWayPartition(self, array, a, b):
		left = 0
		right = len(array) - 1
		i = 0
		while i <= right:
			if array[i] < a:
				(array[left], array[i]) = (array[i], array[left])
				i += 1
				left += 1
			elif array[i] > b:
				(array[right], array[i]) = (array[i], array[right])
				right -= 1
			else:
				i += 1


class Solution:

	def threeWayPartition(self, array, a, b):
		start = 0
		end = n - 1
		i = 0
		while i <= end:
			if array[i] < a:
				(array[i], array[start]) = (array[start], array[i])
				i += 1
				start += 1
			elif array[i] > a:
				(array[i], array[end]) = (array[end], array[i])
				end -= 1
			else:
				i += 1
		return 1


class Solution:

	def threeWayPartition(self, array, a, b):
		array.sort()


class Solution:

	def threeWayPartition(self, array, a, b):
		n = len(array)
		(l, r, mid) = (0, n - 1, 0)
		while mid <= r:
			if array[mid] < a:
				(array[l], array[mid]) = (array[mid], array[l])
				l += 1
				mid += 1
			elif array[mid] > b:
				(array[mid], array[r]) = (array[r], array[mid])
				r -= 1
			else:
				mid += 1
		return array


class Solution:

	def threeWayPartition(self, array, a, b):
		li = [-1] * len(array)
		(j, k) = (0, len(array) - 1)
		for i in array:
			if i < a:
				li[j] = i
				j += 1
			elif i > b:
				li[k] = i
				k -= 1
		for i in array:
			if i >= a and i <= b:
				li[j] = i
				j += 1
		array.clear()
		array = li


class Solution:

	def threeWayPartition(self, array, a, b):
		arr1 = []
		arr2 = []
		arr3 = []
		for i in range(len(array)):
			if array[i] < a:
				arr1.append(array[i])
			elif a <= array[i] <= b:
				arr2.append(array[i])
			else:
				arr3.append(array[i])
		array.clear()
		array = arr1 + arr2 + arr3


class Solution:

	def threeWayPartition(self, arr, a, b):
		i = 0
		j = len(arr) - 1
		for k in range(len(arr)):
			if arr[k] < a:
				(arr[i], arr[k]) = (arr[k], arr[i])
				i += 1
		for k in range(len(arr)):
			if arr[k] > b:
				(arr[k], arr[j]) = (arr[j], arr[k])
				j -= 1
		return