Press "Enter" to skip to content

Posts published in “Divide and Conquer / Dichotomy”

LeetCode 154. Find Minimum in Rotated Sorted Array II

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

  • [4,5,6,7,0,1,4] if it was rotated 4 times.
  • [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

Example 1:

Input: nums = [1,3,5]
Output: 1

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums is sorted and rotated between 1 and n times.

Idea:

Divide and Conquer

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    return searchMin(nums, 0, nums.length - 1);
};

function searchMin(nums, l, r) {
    // exit recursion:
    // only one or two elements in the array
    if (l + 1 >= r)
        return Math.min(nums[l], nums[r]);
    // this array is sorted
    if (nums[l] < nums[r])
        return nums[l];
    
    let mid = l + Math.floor((r - l) / 2);
    return Math.min(searchMin(nums, l , mid), searchMin(nums, mid + 1, r));
}

LeetCode 977. Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example 1:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].

Example 2:

Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Constraints:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums is sorted in non-decreasing order.

Solution 1: (Quick Sort)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums = nums.map(num => num * num);
    quickSort(nums, 0, nums.length - 1);
    return nums;
};

function quickSort(nums, left, right) {
    let index;
    if (nums.length > 1) {
        // index returned from partition
        index = partition(nums, left, right);
        // more elements on the left side of the pivot
        if (left < index - 1)
            quickSort(nums, left, index - 1);
        // more elements on the right side of the pivot
        if (index < right)
            quickSort(nums, index, right);
    }
    // you can return or not return, 
    // since we change nums, no need to return
    // return nums;
}

function partition(nums, start, end) {
    let l = start, r = end;
    let mid = Math.floor((start + end) / 2);
    let pivot = nums[mid];
    // Important: l <= r not l < r
    while (l <= r) {
        while(nums[l] < pivot)
            l++;
        while(nums[r] > pivot)
            r--;
        if (l <= r) {
            // swap
            [nums[l], nums[r]] = [nums[r], nums[l]];
            l++;
            r--;
        }
    }
    return l;
}

Solution 2: (Merge Sort)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortedSquares = function(nums) {
    nums = nums.map(num => num * num);
    let temp = [];
    mergeSort(nums, 0, nums.length - 1, temp);
    return nums;
};

function mergeSort(nums, start, end, temp) {
    if (start >= end) return;
    let mid =  Math.floor((start + end) / 2);
    mergeSort(nums, start, mid, temp);
    mergeSort(nums, mid + 1, end, temp);
    merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
    let mid =  Math.floor((start + end) / 2);
    let l_index = start;
    let r_index = mid + 1;
    let index = start;
    while (l_index <= mid && r_index <= end) {
        if (nums[l_index] < nums[r_index]) {
            temp[index++] = nums[l_index++];
        } else {
             temp[index++] = nums[r_index++];
        }
    }
    while (l_index <= mid) {
        temp[index++] = nums[l_index++];
    }
    while (r_index <= end) {
        temp[index++] = nums[r_index++];
    }
    for (let i = 0; i <= end; i++)
        nums[i] = temp[i];
}

LeetCode 912. Sort an Array (javascript)

Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Constraints:

  • 1 <= nums.length <= 50000
  • -50000 <= nums[i] <= 50000

Idea:

Use Merge Sort Template

Solution:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    if (nums === null || nums.length === 0) return;
    let temp = [];
    mergeSort(nums, 0, nums.length - 1, temp);
    return nums;
};

function mergeSort(nums, start, end, temp) {
    if (start >= end) return;
    // deal with first half
    mergeSort(nums, start, Math.floor((start + end) / 2), temp);
    // deal with second half
    mergeSort(nums, Math.floor((start +end) / 2) + 1, end, temp);
    // merge
    merge(nums, start, end, temp);
}

function merge(nums, start, end, temp) {
    let mid = Math.floor((start + end) / 2);
    let l_index = start;
    let r_index = mid + 1;
    let index = start;
    while (l_index <= mid && r_index <= end) {
        if (nums[l_index] < nums[r_index]) {
            temp[index++] = nums[l_index++];
        } else {
            temp[index++] = nums[r_index++];
        }
    }
    while (l_index <= mid) {
        temp[index++] = nums[l_index++];
    }
    while (r_index <= end) {
        temp[index++] = nums[r_index++];
    }
    for (let i = start; i <= end; i++) {
        nums[i] = temp[i];
    }
}

LeetCode 153. Find Minimum in Rotated Sorted Array (javascript)


Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • All the integers of nums are unique.
  • nums is sorted and rotated between 1 and n times.

Idea:

Use Binary Search Template

  • Time Complexity: O(logN)
  • Space Complexity: O(1)

Solution:

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    // if only have one number
    if (nums.length === 1) return nums[0];
    
    let l = 0;
    let r = nums.length;
    // if this array is sorted
    if (nums[0] < nums[r - 1]) return nums[0];
    
    while (l < r) {
        let mid = l + Math.floor((r - l) / 2);
        
        // if previous element is greater than next element,
        // next element is the smallest
        if (nums[mid] > nums[mid + 1]) 
            return nums[mid + 1];
        if (nums[mid - 1] > nums[mid]) 
            return nums[mid];
        
        // first half is sorted: min is on right side
        if (nums[mid] > nums[0]) 
            l = mid;
        else
            r = mid + 1;
    } 
    return -1;
};

Solution 2:

var findMin = function(nums) {
    return searchMin(nums, 0, nums.length - 1);
};

function searchMin(nums, l, r) {
    // exit recursion:
    // only one or two elements in the array
    if (l + 1 >= r)
        return Math.min(nums[l], nums[r]);
    // this array is sorted
    if (nums[l] < nums[r])
        return nums[l];
    
    let mid = l + Math.floor((r - l) / 2);
    return Math.min(searchMin(nums, l , mid), searchMin(nums, mid + 1, r));
}

LeetCode 169. Majority Element (javascript)

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Constraints:

  • n == nums.length
  • 1 <= n <= 5 * 104
  • -231 <= nums[i] <= 231 - 1

Solution 1: (Hash Table)

  • Time Complexity : O(n)
  • Space Complexity : O(n)
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let map = new Map();
    for (let num of nums) {
        map.set(num, (map.has(num) ? map.get(num) : 0)  + 1);
        if (map.get(num) > nums.length / 2) return num;
    }
    return -1;
};

Solution 2: (Sorting)

  • Time Complexity : O(n)
  • Space Complexity : O(1)
var majorityElement = function(nums) {
    nums.sort();
    return nums[Math.floor(nums.length / 2)];
};

Solution 3: (Divide and conquer)

  • Time Complexity : O(nlogn)
  • Space Complexity : O(logn)
var majorityElement = function(nums) {
    return majority(nums, 0, nums.length - 1);
};

function majority(nums, l, r) {
    if (l === r) return nums[l];
    const mid = l + Math.floor((r - l) / 2);
    const left = majority(nums, l , mid);
    const right = majority(nums, mid + 1, r);
    if (left === right) return left;
    return nums.slice(l, r + 1).filter(x => x === left).length >
           nums.slice(l, r + 1).filter(x => x === right).length
           ? left : right;
}

LeetCode 34. Find First and Last Position of Element in Sorted Array (javascript)


Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109

Idea:

Binary Search

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let leftBound = -1;
    let rightBound = -1;
    let l = 0;
    let r = nums.length - 1;
    
    while (l <= r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            leftBound = mid;
            r = mid - 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    
    l = 0;
    r = nums.length - 1;
    while (l <= r) {
        let mid = l + Math.floor((r - l) / 2);
        if (nums[mid] === target) {
            rightBound = mid;
            l = mid + 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return [leftBound, rightBound];
};

LeetCode 33. Search in Rotated Sorted Array (javascript)

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

Idea:

Binary Search: the idea is to create a recursive function that takes l and h as range in input and the key.

1) Find middle point mid = (l + h)/2
2) If key is present at middle point, return mid.
   Edge case check(not found): if (l > h) return -1;
3) Else If nums[l..mid] is sorted
    a) If key to be searched lies in range from nums[l]
       to nums[mid], recur for nums[l..mid].
    b) Else recur for nums[mid+1..h]
4) Else (nums[mid+1..h] must be sorted)
    a) If key to be searched lies in range from nums[mid+1]
       to nums[h], recur for nums[mid+1..h].
    b) Else recur for nums[l..mid] 

Solution:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    return searching(nums, 0, nums.length - 1, target);
};

function searching(nums, l, h, target) {
    // basic case: not found
    if (l > h) return -1;
    
    let mid = Math.floor((l + h) / 2);
    // basic case: found
    if (target === nums[mid]) return mid;
    
    // if nums[l...mid] is sorted
    if (nums[l] <= nums[mid]) { /// make sure is <=
        if (target >= nums[l] && target <= nums[mid])
            return searching(nums, l, mid - 1, target);
        else
            return searching(nums, mid + 1, h, target)
    }
    
    // if nums[l...mid] is notesorted, then nums[mid+1..h] must be sorted
    if (target >= nums[mid] && target <= nums[h])
        return searching(nums, mid + 1, h, target);
    else
        return searching(nums, l, mid - 1, target);
}

LeetCode 23. Merge k Sorted Lists (javascript)

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length won’t exceed 10^4.

Idea:

Divide and Conquer

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    return merge(lists, 0, lists.length - 1);
};

function merge(lists, l , r) {
    if (lists.length === 0) return null;
    if (l === r) return lists[l];
    let mid = Math.floor((l + r) / 2);
    let l1 = merge(lists, l, mid);
    let l2 = merge(lists, mid + 1, r);
    return mergeTwoLists(l1, l2);
}

var mergeTwoLists = function(l1, l2) {
    // If one of the list is empty, return the other one.
      if (l1 === null) {
        return l2;
      }
      if (l2 === null) {
        return l1;
      }
    
    // The smaller one becomes the head.
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};