Be the first user to complete this post

  • 0
 Add to List
Medium

475. Sort the two dimensional (2D) array - In-place

Problem: Given a two-dimensional array where each individual row is sorted in ascending order. Your task to sort the entire 2d array in ascending order. Write an algorithm for the sorting.

Example:

Given Array:
[[5, 12, 17, 21, 23]
[1, 2, 4, 6, 8]
[12, 14, 18, 19, 27]
[3, 7, 9, 15, 25]]

Sorted Array:
[[1, 2, 3, 4, 5]
[6, 7, 8, 9, 12]
[12, 14, 15, 17, 18]
[19, 21, 23, 25, 27]]

Approach:

  1. Each row is sorted, we will take advantage of this. 
  2. Since each row is sorted which means the first column for each row will have the minimum element among their respective rows, which also means that minimum element in the entire matrix will be from the first column. So we will pick that smallest element and replace it with the first element in the matrix. 
  3. Now we have successfully placed the right element at the first position in the array. Now we will restore the original property of the array which is each row is sorted. So we will shift the swapped element (earlier with the first position of the matrix) till it finds its right place in the array. 
  4. Now we need to find the second most minimum element for the second position which will be among elements at the second column in the first row and first column in the rest of the rows. Once found, swap it and again reorder to restore the original property.
  5. Repeat this process until the entire array is sorted.

See the example below for more understanding- 

Output:

Given Array:
Given Array:
5   12   17   21   23
1   2   4   6   8
12   14   18   19   27
3   7   9   15   25
Sorted Array:
1   2   3   4   5
6   7   8   9   12
12   14   15   17   18
19   21   23   25   27

Related Problems: