👋 Hello, and welcome guys to an amazing series of competitive programming. In our previous blogs, we have studied some amazing array algorithms, and have solved problems based on corresponding algorithms. Apart from this we have also started with competitive topics and have covered Recursion and Backtracking. After this, the most important topic is sorting, and I hope that you are aware of sorting algorithms like Bubble sort, Insertion sort, Merge sort, quick sort, etc. If you do not know any of the sorting algorithms then I will request you to please study sorting algorithms first which are present in huge amounts on the web but how questions based on these algorithms are asked and how to approach them is not present on the web so the main motive of this blog is to introduce you to some popular coding problems on sorting and how to approach them.
Table of Contents
1) Sort the Array by Kth bit
Given an array of N number of integers, and an integer K. Your task is to group the array elements by Kth bit (rightmost bit is 1st bit) in such a way that all the elements come first whose Kth bit is 0 followed by elements with K bit as 1.
Note ~
- The relative order inside both groups should be the same. It means the order in which elements are present in an original array then after sorting if their Kth bit is 0 then they should be in the same order and the same when the Kth bit is 1.
- Elements whose binary representation is less the length of k then there Kth bit is 0 only.
Sample Inputs and Outputs
The first line has a number of test cases. For each test case, we have N and k followed by N number of elements in the next line. Return the modified array by sorting it by Kth bit.
How would you approach this problem?
The basic approach we all can think that we will make one empty array say as a result of size N and one temporary empty arrays. Then we will iterate over an array and convert decimal to binary and check its Kth bit. If it is equal to 0 then add it to a resultant array, else add it to a temporary array. After iteration add all the remaining elements from the temporary array to the resultant array.
def decimalToBinary(n):
return bin(n).replace("0b", "")
def sortArrayByKBit(n, k, arr):
res = []
rem = []
for i in range(n):
bn = decimalToBinary(arr[i])
bn = bn[::-1]
if len(bn) < k or bn[k-1] == "0":
res.append(arr[i])
else:
rem.append(arr[i])
res.extend(rem)
return res
Simplified Approach
The approach is the same as iteration but we can simplify it more so that our code does not reach TLE(time limit exceed) because above we are using an in-built binary function or loop to convert decimal to binary. Apart from this, we are using 2 extra arrays. So instead of using loops, use bitwise operators that can directly check the Kth bit. Perform an operation between number and left shift of number with one. And if it's equal to 0 then add the element in the same array from the beginning else add to any other temporary array. This will help run the code in a given time.
def sortArrayByKBit(n, k, arr):
p = 0 #track original array
j = 0 #track temporary array
temparr = [0]*n
for i in range(n):
#If Kth bit is 0
if((arr[i] & (1 << (k-1))) == 0):
arr[p] = arr[i]
p += 1
else:
temparr[j] = arr[i]
j += 1
#copy all element from temparr to arr
j = 0
for i in range(p, n):
arr[i] = temparr[j]
j += 1
return arr
2) Sort The array in Waveform
This is a simple question that you can solve. Given an unsorted array of N integers. Your task is to sort the array in such a way that it looks like a wave array. Observe the below gist to understand what is wave array.
Sample Inputs and Outputs
Given T number of test cases. The first line of each test case denotes the number of elements in the array followed by array elements in the second line. Return the wave array.
Sorting Approach to convert an array into wave array
In this approach, we first sort the array then swap the adjacent elements of the array. Suppose we have an array as {1, 4, 3, 2, 6, 5, 8}. So its sorted form is {1, 2, 3, 4, 5, 6, 8}. Then swap adjacent elements that mean after skipping one element swap two-element so array form is {2, 1, 4, 3, 6, 5, 8}. Now the array is in wave form. We can say that arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= arr[5] <= arr[6].
Hence time complexity becomes (N + N/2) = O(N). Let us implement the algorithm.
def waveFormArray(arr, n):
# sort the arr (you can use any sort algorithm)
arr.sort()
# swap adjacent element run loop i+2
for i in range(1, n, 2):
arr[i-1], arr[i] = arr[i], arr[i-1]
return arr
3) Sort An Array according to the count of set bits
Given an array of N positive integers. Your task is to sort the array in decreasing order according to a count of set bits in a binary representation. In simple words, you have to modify the array in such a way that the integer which has more numbers of one(set bits) in binary representation should come first than the integer that has fewer set bits.
Note -
The elements that have the same number of set bits keep them in the original order as in array means to maintain stable sorting.
Sample Inputs and Outputs
Given T number of test cases. The first line of each test case contains integer N denoting the size of the array followed by the array element in the next line.
Multimap Approach
The approach is simple to maintain a pair of multimaps where the key is a count of set bit and element value and then sort the map according to a count of bits. Then traverse the map from the beginning and modify the array.
Count Sort Approach to sort array according to count of set bits
It is an interesting solution that can solve the problem in O(N) time and is very similar to the counting sort algorithm. There can be a minimum of 1 set bit and a maximum of 31 set bits in an integer.
- Create a vector(List of the list) of size 32 as bits count. Each cell of the vector[I] stores the element that has total set bits equal to I.
- To create the vector traverse the array and for each element counts the number of set bits and append an element at the count index of a vector.
- Now traverse the vector from the end as we have to create a non-increasing array and modify the array.
Let us build the algorithm using Python and the snippet is shown below.
def countSetBits(num):
cnt = 0
while num != 0:
cnt = cnt + (num & 1)
num = num >> 1
return cnt
def sortSetBitsCount(arr, size):
#vector of size 32
bitscount = [[] for i in range(32)]
val = 0
#store count of each bit
for i in range(size):
val = countSetBits(arr[i])
bitscount[val].append(arr[i])
j = 0 #used as an idx in final sorted arr
for i in range(31, -1, -1):
v1 = bitscount[i]
for k in range(len(v1)):
arr[j] = v1[k]
j += 1
return arr
t = int(input())
while t > 0:
n = int(input())
arr = list(map(int, input().split()))
ans = sortSetBitsCount(arr, n)
print(*ans)
t = t-1
4) Sort a Half-Sorted Array
Given an array of N integers that consist of two partitions sorted in non-decreasing order. Your task is to sort an entire array in ascending order. In simple words, you are given an array in which elements are divided into two partitions such that both partitions are separately sorted. You need to sort an entire array. Note that you have to update the given array in-self.
Sample Inputs and Outputs
The first line contains a single integer T denoting the number of test cases. For each test case, the first line contains integer N denotes the size of the array, and in the next line given N number of elements of an array. Return the sorted array.
Naive Approach to solve Half-Sorted array problem
What you would think is at the end we want a sorted array so we can use any sorting algorithm that sorts the array in O(N^2) or O(N) time. The approach will totally work fine and might clear all the test cases. But this will work when you got this question in a coding contest or competitive programming and will not work when you are appearing for a technical interview. So let's see what other approach we can use.
Use Merge Function of Merge Sort Algorithm
If you know the merge sort algorithm then this approach will be pretty clear to you. In merge sort, we divide the array into halves and sort the single half and then merge each half in the sorted form to obtain a complete sorted array.
- First, form an empty temporary array of size N that will be used to store the final sorted array.
- Now, first, we find the pivot point in a given array. This is a point where the second partition begins. To find pivot we only need to check arr[I] > arr[i+1] then i+1 is the pivot point.
- If the pivot is 0 that means the array has only one partition which is sorted so return the original array.
- Else we use a while loop to keep storing elements in a temporary array in a sorted array by picking one element at a time from both partitions till I<pivot and pivot < N. For this we use three variables as i=0 for traversing the first partition, J=pivot for traversing the second partition, and k=0 to keep track of temporary array.
- Finally copy the elements of a temporary array to the original array.
Code snippet of this algorithm is implemented below.
def sortHalfSorted(arr):
pivot, n = 0, len(arr)
temp = [0 for i in range(n)]
#find pivot point
for i in range(n-1):
if arr[i] > arr[i+1]:
pivot = i+1
break
#if pivot equals 0 then return
if pivot == 0:
return
#sort an array
i, j, k = 0, pivot, 0
while i < pivot and j < n:
if arr[i] < arr[j]:
temp[k] = arr[i]
k += 1
i += 1
else:
temp[k] = arr[j]
k += 1
j += 1
#copy remaining ele of 1st partition
while i < pivot:
temp[k] = arr[i]
k += 1
i += 1
#copy remaining ele of 2nd partition
while j < n:
temp[k] = arr[j]
k += 1
j += 1
#copy temp array to original array
for i in range(n):
arr[i] = temp[i]
5) Minimum Number of Swaps Required to sort an array
Given an array of N distinct integers. Your task is to find a minimum number of swaps required to sort an array.
Sample Input and Output
The first line contains T denoting the number of test cases. Each test case contains N representing the size of the array followed by distinct array elements in the next line.
Approach to find minimum swaps required to sort the array
The approach is simple like we will keep a sorted form of an array with us in a temporary array. And we will also create a map that will store the index of each element in an array. Now we will iterate in an array and at each index, we will that element at that index in the original array and a sorted array is equal or not. If equal then nothing to do but if not equal then swap operation is required. Now how we will swap is we want a correct element to insert there which we will find in an array using map-like using map we will find an index of a correct element in an array and swap the current element with the correct element index in the array and update the index in map. Whenever we require swapping increase the count of minimum swaps. let us understand the approach in a step-wise manner with example.
- Suppose we have array as {1, 5, 4, 3, 2}. So the sorted order temp = {1, 2, 3, 4, 5} and map = {1:0, 5:1, 4:2, 3:3, 2:4}.
- As we iterate in array first element is the same. But second element 5 is not equal to 2. So we extract an index of 2 from an array using a map which is 4. We will swap elements in the array at index 1 and at index 4. So the array becomes {1, 2, 4, 3, 5} and update the map so it become {1:0, 5:4, 4:2, 3:3, 2:1}. The count of minimum swap becomes 1.
- The next 4 are not equal to 3. Again swap array elements at index 2 and index 3. Array form is {1, 2, 3, 4, 5} and map become {1:0, 5:1, 4:3, 3:2, 2:4}. Count increases to 2.
- Now the array is in sorted form and returns the count.
👉 Try to implement the algorithm and you can take reference using the below snippet.
def minSwaps(arr):
hashmap = {}
min_swaps = 0
temp = arr.copy() # we create a copy so not change in original array
temp.sort() #sort the array
n = len(arr)
#create map
for i in range(n):
hashmap[arr[i]] = i
for i in range(n):
if arr[i] != temp[i]:
min_swaps += 1
curr_ele = arr[i]
idx = hashmap[temp[i]]
arr[i], arr[idx] = arr[idx], arr[i] #swap in array
#update hashmap of both swaped element
hashmap[curr_ele] = hashmap[temp[i]]
hashmap[temp[i]] = i
return min_swaps
End Notes
Hurray! We have covered some of the popular problems based on sorting techniques. I hope that you came to understand how to use sorting in array coding problems and identify that sorting can help us reach the solution easier. Now using the reference to these 5 coding problems you can develop an approach and solve many other coding problems and you should try them on leetcode, HackerRank, or on coding Ninjas. If you have any doubts left please post them in the comment section below, and if you have any new questions then also feel free to post them and you can also contact us using this contact form.
Thanks for your time! 😊