# Posts published in “Divide and Conquer / Dichotomy”

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));
}``````

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];
}``````

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];
}
}``````

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));
}``````

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;
}``````

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];
};``````

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.
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) {
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);
}``````

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

Example 1:

```Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
[
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:

``````/**
* 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;
}
};``````