Sort an Array (Leetcode 912)
Minimum remove to make valid parentheses (Leetcode 1249)
Bias-variance equation
Minimum remove to make valid parentheses (Leetcode 1249)
Bias-variance equation
O(nlog(n)) time complexity and with the smallest space complexity possible.
Examples:
Input:
[5, 2, 8, 1, 9]Output:
[1, 2, 5, 8, 9]
Input:
[5]Output:
[5]
The base case is when we reach an array of one element that we cannot further split. A single-element array is sorted by definition.
The recursive relationship is that we can merge two sorted arrays.
Hence, we can keep splitting until we reach single-element arrays and then start merging all the way to the top.
from typing import List
def sort_array(nums: List[int]) -> List[int]:
def merge(sortedArr1, sortedArr2):
i, j = 0, 0
n1, n2 = len(sortedArr1), len(sortedArr2)
ans = []
while i < n1 and j < n2:
if sortedArr1[i] < sortedArr2[j]:
ans.append(sortedArr1[i])
i += 1
else:
ans.append(sortedArr2[j])
j += 1
if j < n2:
i = j
sortedArr1 = sortedArr2
for k in range(i, len(sortedArr1)):
ans.append(sortedArr1[k])
return ans
def mergsort(a):
n = len(a)
if n == 1:
return a
a1, a2 = a[: n // 2], a[n // 2 :]
return merge(mergsort(a1), mergsort(a2))
return mergsort(nums)
We can run an example as follows:
## [1, 2, 5, 8, 9]
The time complexity of this solution is \(O(N log N)\). We divide in \(O(log N)\) and then we merge those halves which will take \(O(N)\) so \(O(N log N)\). Space complexity is \(O(N)\), since the recursive stack will use \(O(log N)\) and we also use an additional array
ansof space \(O(N)\).
Recursion, Sorting
- Search in Binary Search Tree (Leetcode 700) Easy (Binary Search, Binary Search Tree)
- Number of recent calls (Leetcode 933) Easy (Queue, DEQueue)
- Find if Path Exists in Graph (Leetcode 1971) Medium (DFS, BFS)
- Longest substring without repeating characters (Leetcode 3) Medium (Hash, Sliding Window)
- Climbing stairs (Leetcode 70) Easy (Recursion, Dynamic programming)
Thank you, we have received your feedback.