# Posts tagged as “divide and conquer”

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, a, a, ..., a[n-1]]` 1 time results in the array `[a[n-1], a, a, a, ..., 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 the `head` of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in `O(n logn)` time and `O(1)` memory (i.e. constant space)?

Example 1:

```Input: head = [4,2,1,3]
Output: [1,2,3,4]
```

Example 2:

```Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
```

Example 3:

```Input: head = []
Output: []
```

Constraints:

• The number of nodes in the list is in the range `[0, 5 * 104]`.
• `-105 <= Node.val <= 105`

Idea:

Merge Sort (use slow and fast pointer to find the middle of the linked list and split them)

Time Complexity: O(nlogn)

Solution:

``````/**
* function ListNode(val, next) {
*     this.val = (val===undefined ? 0 : val)
*     this.next = (next===undefined ? null : next)
* }
*/
/**
* @return {ListNode}
*/
// empty or one node
let right = sortList(mid);
return merge(left, right);
};

function merge(list1, list2) {
let tail = new ListNode();
while (list1 !== null && list2 !== null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
tail = tail.next;
} else {
tail.next = list2;
list2 = list2.next;
tail = tail.next;
}
}
tail.next = (list1 !== null) ? list1 : list2;
};

while (fast !== null && fast.next !== null) {
slow = slow.next
fast = fast.next.next;
}
// !!!Important here:
// disconnect, split them into two lists
return secondHalf;
}``````

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, a, a, ..., a[n-1]]` 1 time results in the array `[a[n-1], a, a, a, ..., 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;

let l = 0;
let r = nums.length;
// if this array is sorted
if (nums < nums[r - 1]) return nums;

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)
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, nums, ..., 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 = , 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;
}
};``````