Leetcode Sorting Problem Notes
Contents
Leetcode 21: Merge Two Sorted Lists
Problem statement
Merge two sorted linked lists into a new sorted linked list and return it. The new list is formed by joining all the nodes from the two given lists.
Example:
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
Approach
This is the merge operation in merge sort, applied to linked lists.
Code
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = new ListNode(-1);
ListNode head = res;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
head.next = l1;
head = head.next;
l1 = l1.next;
}
else{
head.next = l2;
head = head.next;
l2 = l2.next;
}
}
while(l1 != null){
head.next = l1;
head = l1;
l1 = l1.next;
}
while(l2 != null){
head.next = l2;
head = l2;
l2 = l2.next;
}
return res.next;
}
}
Leetcode 912: Sort an Array
Problem statement
Given an integer array nums, sort it in ascending order.
Example 1:
Input: [5,2,3,1] Output: [1,2,3,5] Example 2:
Input: [5,1,1,2,0,0] Output: [0,0,1,1,2,5]
Approach
This is a standard array-sorting problem, and it can also serve as a performance test for different sorting algorithms. Of the algorithms I submitted, quicksort performed best.
Code
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums);
return nums;
}
private void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int start, int end) {
if (start >= end) return;
int k = partition(arr, start, end);
quickSort(arr, start, k - 1);
quickSort(arr, k + 1, end);
}
private int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private void swap(int[] arr, int a, int b) {
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
Leetcode 378: Kth Smallest Element in a Sorted Matrix
Problem statement
Given an n x n matrix with each row and column sorted in ascending order, find the kth smallest element in the matrix. Note that this is the kth smallest element after sorting, not the kth element.
Example:
matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8,
Return 13. Notes: You may assume k is always valid, 1 ≤ k ≤ n2.
Approach
My first thought was a topK algorithm. We just need to flatten the two-dimensional matrix into a one-dimensional array first. Here is the code:
class Solution {
private void swap(int[] arr, int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
private int partition(int[] arr, int lo, int hi){
int count = lo, j = hi;
int pivot = arr[hi];
for(int i = lo; i < hi; i++){
if(arr[i] < pivot){
swap(arr, i , count);
count++;
}
}
swap(arr, count, hi);
return count;
}
private int select(int[] arr, int k){
int lo = 0, hi = arr.length -1;
while(lo < hi){
int j = partition(arr, lo, hi);
if(j < k){
lo = j + 1;
}
else if( j > k ){
hi = j -1;
}
else{
return arr[k];
}
}
return arr[k];
}
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int[] arr = new int[n * n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
arr[i * n + j] = matrix[i][j];
}
}
int res = 0;
res = select(arr, k - 1);
return res;
}
}
A topk problem can also be solved with a heap. Java’s priority queue is heap-based and uses natural ordering by default, from smallest to largest. Since Java’s priorityQueue only lets us retrieve values through peek() and poll(), we need to maintain a heap of length - k+ 1 elements. For example, finding the 8th smallest of 9 elements is equivalent to finding the 2nd (9 - 8 + 1) largest of those 9 elements.
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int size = matrix.length;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < size; i++){
for(int j = 0; j < size; j++){
pq.add(matrix[i][j]);
if(pq.size() > size*size - k + 1) pq.poll();
}
}
return pq.peek();
}
}
Leetcode 148: Sort List
Problem statement
Sort a linked list in O(n log n) time and constant space.
Example 1:
Input: 4->2->1->3 Output: 1->2->3->4 Example 2:
Input: -1->5->3->4->0 Output: -1->0->3->4->5
Approach
1: An intuitive approach is to convert the linked list into an array, sort it, and then reconstruct the linked list.
class Solution {
public ListNode sortList(ListNode head) {
List<Integer> arr = new ArrayList<>();
ListNode tmp = head;
while(tmp!= null){
arr.add(tmp.val);
tmp = tmp.next;
}
Collections.sort(arr);
tmp = head;
int idx = 0;
while(tmp != null){
tmp.val = arr.get(idx++);
tmp = tmp.next;
}
return head;
}
}
2: Of course, we can also implement quicksort and merge sort directly on linked lists. Quicksort involves many swaps, while merge sort only copies between adjacent elements, so merge sort is a little easier to implement and more efficient. See Leetcode 21 for the merge operation.
Code
class Solution {
public ListNode sortList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
ListNode mid = slow.next;
slow.next = null;
return mergeTwoLists(sortList(head),sortList(mid));
}
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = new ListNode(-1);
ListNode head = res;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
head.next = l1;
head = head.next;
l1 = l1.next;
}
else{
head.next = l2;
head = head.next;
l2 = l2.next;
}
}
while(l1 != null){
head.next = l1;
head = l1;
l1 = l1.next;
}
while(l2 != null){
head.next = l2;
head = l2;
l2 = l2.next;
}
return res.next;
}
}
Leetcode 88: Merge Sorted Array
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 so that num1 becomes a sorted array.
Notes:
The initial numbers of elements in nums1 and nums2 are m and n, respectively. You may assume nums1 has enough space (at least m + n) to hold the elements of nums2. Example:
Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Approach
The merge operation on arrays.
Code
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] aux = nums1.clone();
int i = 0, j = 0;
int idx = 0;
while(i < m && j < n){
if(aux[i] < nums2[j]){
nums1[idx] = aux[i];
i++;
}
else{
nums1[idx] = nums2[j];
j++;
}
idx++;
}
while(i < m){
nums1[idx] = aux[i];
idx++;
i++;
}
while( j < n){
nums1[idx] = nums2[j];
idx++;
j++;
}
}
}
Leetcode 280: Wiggle Sort
Problem statement
Given an unsorted array nums, rearrange it in place so that nums[0] <= nums[1] >= nums[2] <= nums[3]…
Example:
Input: nums = [3,5,2,1,6,4] Output: One possible solution is [3,5,1,6,2,4].
Approach:
- Sort the array first, then swap each pair of elements starting from the second element.
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
for(int i = 1; i < nums.length - 1; i+= 2){
swap(nums, i , i+ 1);
}
}
private void swap(int[] arr, int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
- The second approach asks whether we can put the array into wiggle order step by step. We can express wiggle order as follows: when i is even, nums[i] <= nums[i + 1]; when i is odd, nums[i]>= nums[i +1]. If the actual order is reversed, a single swap achieves the required order without disrupting the portion already arranged.
class Solution {
public void wiggleSort(int[] nums) {
for(int i = 0; i < nums.length - 1; i++){
if((i % 2 == 1 && nums[i] < nums[i + 1])|| (i % 2 == 0 && nums[i]> nums[i+ 1])){
swap(nums, i, i + 1);
}
}
}
private void swap(int[] arr, int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
Leetcode 324: Wiggle Sort II
Problem statement
Given an unsorted array nums, rearrange it into the order nums[0] < nums[1] > nums[2] < nums[3]…
Example 1:
Input: nums = [1, 5, 1, 1, 6, 4] Output: One possible answer is [1, 4, 1, 5, 1, 6]. Example 2:
Input: nums = [1, 3, 2, 2, 3, 1] Output: One possible answer is [2, 3, 1, 3, 1, 2].
Approach
Compared with Leetcode 280, this problem has a stricter requirement: equality is no longer allowed. The previous method therefore does not work, but we can still sort first and then construct the result. We could split the array in half and interleave the second half with the first. However, this fails the test case [4，5， 5， 6]. We need to reverse both halves before interleaving the second with the first. That works.
Reference solution
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int[] aux = nums.clone();
int n = nums.length;
int j = (n-1)/2, k = n - 1;
for(int i = 0; i< n ; i++){
if(i % 2 == 0){
nums[i] = aux[j];
j--;
}
else{
nums[i] = aux[k];
k--;
}
}
}
}
- The algorithm above has O(nlogn) time complexity, while the follow-up requires O(n). How can we achieve that? Sorting is certainly out, but we still need to ensure the interleaved order. A topK algorithm fits this requirement. We just need to use topk to partition the array into values less than median, equal to median, and greater than median. The remaining steps are the same as above.
Reference solution
class Solution {
private int quickSelect(int[] arr, int k){
int lo = 0, hi = arr.length -1;
while(lo <= hi){
int j = partition(arr, lo, hi);
if( j == k ) return arr[j];
if( j < k){
lo = j + 1;
}
else{
hi = j - 1;
}
}
return -1;
}
private int partition(int[] arr, int lo, int hi){
int count = lo;
int pivot = arr[hi];
for(int i = lo; i < hi; i++){
if(arr[i] < pivot){
swap(arr, count, i);
count++;
}
}
swap(arr, count , hi);
return count;
}
public void wiggleSort(int[] nums) {
int n = nums.length;
int median = quickSelect(nums,n/2 );
int[] aux =new int[n];
int left = 0, right = n - 1;
for(int i = 0 ; i < n; i++){
if(nums[i] < median){
aux[left] = nums[i];
left++;
}
else if(nums[i] > median) {
aux[right] = nums[i];
right--;
}
}
for(int i = left ; i <= right; i++){
aux[i] = median;
}
left = (n- 1)/2;
right = n - 1;
for (int i = 0; i < n; i++) {
if ( i % 2 == 0) {
nums[i] = aux[left];
left--;
} else {
nums[i] = aux[right];
right--;
}
}
}
private void swap(int[] arr, int a, int b){
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
}
Reducing the space complexity to O(1) requires index mapping. Also, this O(n) algorithm is actually slower on Leetcode than the O(nlogn) algorithm.
Leetcode 1122: Relative Sort Array
Problem statement
Given two arrays, arr1 and arr2,
the elements of arr2 are distinct, and every element in arr2 also appears in arr1. Sort the elements of arr1 so that their relative order matches the relative order in arr2. Elements absent from arr2 should be placed at the end of arr1 in ascending order.
Example:
Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] Output: [2,2,2,1,4,3,3,9,6,7,19]
Constraints:
arr1.length, arr2.length <= 1000 0 <= arr1[i], arr2[i] <= 1000 The elements arr2[i] in arr2 are distinct. Every element arr2[i] in arr2 appears in arr1.
Approach
We can use a map<value, count> to sort arr1. Since the values in arr1 have a small range, we can use a numeric value directly instead of a map. Place the numbers from arr2 first, removing them from the map as we go, then arrange the remaining elements.
Reference solution
class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] cnt = new int[1001];
for(int num : arr1){
cnt[num]++;
}
int idx = 0;
for(int num : arr2){
while(cnt[num] > 0){
arr1[idx++] = num;
cnt[num]--;
}
}
for(int i= 0; i < 1001; i++){
while(cnt[i] > 0){
arr1[idx++] = i;
cnt[i]--;
}
}
return arr1;
}
}
Leetcode 147: Insertion Sort List
Problem statement:
Perform insertion sort on a linked list.
The animation above demonstrates insertion sort. Starting with the first element, the linked list can be considered partially sorted (shown in black). At each iteration, one element is removed from the input data (shown in red) and inserted in place into the sorted linked list.
The insertion sort algorithm:
Insertion sort is iterative, moving one element at a time until all elements form a sorted output list. At each iteration, insertion sort removes just one unsorted element from the input, finds its proper position in the sequence, and inserts it. Repeat until all input elements have been inserted.
Approach
Follow the array version of InsertSort. Pay attention to inserting before head and to the order in which ListNode next pointers are updated.
Reference solution
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode curr = head;
while(curr != null&& curr.next != null){
ListNode tmp = curr.next;
while(tmp != null && tmp.val < curr.val){
curr.next = tmp.next;
insert(dummyHead, tmp);
tmp = curr.next;
}
curr= curr.next;
}
return dummyHead.next;
}
private void insert(ListNode dummyHead, ListNode tmp){
ListNode pre = dummyHead;
while(pre.next.val <= tmp.val){
pre = pre.next;
}
tmp.next = pre.next;
pre.next = tmp;
}
}