Educative Modules
[[1-SlidingWindow]] [[DSAX-Modules/educative.io/2-RotatedArray]]
Last active
November 29, 2021 05:42
-
-
Save wxgrzr/6deb39b4bde1c6078321a0ffba0e6da5 to your computer and use it in GitHub Desktop.
Educative-Modules
Given a large array of integers and a window size of w find the current maximum value in the window as the window slides through the entire array.
Let's try to find all maximums for w = 3:
[-4, 2, -5, 3, 6]
Step 1: for the first 3 elements, max is 2.
[-4, 2, -5], 3, 6
*
Step 2: Slide window one position to right and the max is now 3
-4, [2, -5, 3], 6
*
Step 3: In the last window the max is 6.
-4, 2, [-5, 3, 6]
let ffindMaxSlidingWindow = function(arr, windowSize) {
let result = []
if (arr.length == 0){
return result;
}
if (windowSize > arr.length) {
return result;
}
let window_ = 0;
// find max for first window
for (let i = 0; i < windowSize; i++) {
while(window_.length > 0 && arr[i] >= arr[window_[window_.length - 1]]){
window_.pop();
}
window.push(i);
}
result.push(arr[window_[0]])
for (let i = windowSize; i < arr.length; i++){
// remove all numbers that are smaller than the current max from the list
while (window_.length > 0 && arr[i] >= arr[window_[window_.length -1]]) {
window_.pop();
}
// remove first number if it doesn't fall in window
if (window_.length > 0 && (window_[0] <= i - windowSize>)){
window_.shift();
}
window_.push(i)
result.push(arr[window_[0]])
}
return result;
}
let array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log("Array = " + array);
console.log("Max = " + ffindMaxSlidingWindow(array, 3));
// Max = 3,4,5,6,7,8,9,10
let array1 = [10, 6, 9, -3, 23, -1, 34, 56, 67, -1, -4, -8, -2, 9, 10, 34, 67]
console.log("Array = " + array1);
console.log("Max = " + ffindMaxSlidingWindow(array1, 3))
// Max = 10,9,23,23,34,56,67,67,67,-1,-2,9,10,34,67
The runtime complexity in linear, O(n).
Every element is pushed and popped from the deque only once in a single traversal.
Memory complexity is linear, O*(w), where w is the window size
[[0-Index]]
Search for number in sorted array, with unique elements, that has been rotated by some arbitrary number. Return
-1if it doesn't exist
**Assume array does not contain duplicates
- Linear Search is not an acceptable solution
- Try to solve with binary search
Note: binary search requres a sorted array
const values = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
const search = (val, arr) => {
for (let i = 0; i < arr.length; i++) {
if(val === arr[i]) {
return i;
}
}
return -1;
}- Always dealing with
lowerandupperlimits - Cut at middle, if not found, split sides at middle of each side until found
const binary = (val, arr) => {
// create lower value
let lower = 0;
// create upper value
let upper = arr.length - 1;
// keep iterating as long as lower boundary is less than upper boundary
while(lower <= upper) {
// get middle index of array
const middle = lower + Math.floor((upper - lower)/2)
// if search val is middle # between lower and upper, return middle
if (val === arr[middle]){
return middle;
}
/* if search val is less than middle number:
1. set upper to middle - 1
2. set lower to middle + 1
*/
if (val < arr[middle]){
upper = middle - 1;
} else {
lower = middle + 1;
}
}
return -1;
}1. Sorted array
2. Cut in half
3. Proceed to left;
search left
4. Proceed to right;
search right
5. Repeat
Issue: Only one half of the array remains sorted if rotated
- If number
nis within sorted half, it is a basic binary search - Otherwise, discard sorted half and keep unsorted to be examine
-- Since we're partitioning each step, O(log n)
Solution 1: Recursive
let binarySearch = function(arr, start, end, key) {
// assuming all the keys are unique.
if (start > end) {
return -1;
}
let mid = start + Math.floor((end - start) / 2);
if (arr[mid] === key) {
return mid;
}
if (arr[start] <= arr[mid] && key <= arr[mid] && key >= arr[start]) {
return binarySearch(arr, start, mid - 1, key);
}
else if (arr[mid] <= arr[end] && key >= arr[mid] && key <= arr[end]) {
return binarySearch(arr, mid + 1, end, key);
}
else if (arr[end] <= arr[mid]) {
return binarySearch(arr, mid + 1, end, key);
}
else if (arr[start] >= arr[mid]) {
return binarySearch(arr, start, mid - 1, key);
}
return -1;
};
let binarySearchRotated = function(arr, key) {
return binarySearch(arr, 0, arr.length - 1, key);
};
let v1 = [6, 7, 1, 2, 3, 4, 5];
console.log("Key(3) found at: " + binarySearchRotated(v1, 3));
console.log("Key(6) found at: " + binarySearchRotated(v1, 6));
let v2 = [4, 5, 6, 1, 2, 3];
console.log("Key(3) found at: " + binarySearchRotated(v2, 3));
console.log("Key(6) found at: " + binarySearchRotated(v2, 6));Solution 2: Iterative
The runtime complexity of this solution is logarithmic
O(log n).
The memory complexity of this solution is constant
O(1).
let binarySearchRotated = function(arr, key) {
start = 0;
end = arr.length - 1;
if (start > end){
return -1;
}
while (start <= end){
mid = start + Math.floor((end - start) / 2);
if (arr[mid] == key){
return mid;
}
if (arr[start] <= arr[mid] && key <= arr[mid] && key >= arr[start]){
end = mid - 1;
}
else if (arr[mid] <= arr[end] && key >= arr[mid] && key <= arr[end]){
start = mid + 1;
}
else if (arr[end] <= arr[mid]){
start = mid + 1;
}
else if (arr[start] >= arr[mid]){
end = mid - 1;
}
else{
return -1;
}
}
return -1;
};
let v1 = [6, 7, 1, 2, 3, 4, 5];
console.log("Key(3) found at: " + binarySearchRotated(v1, 3));
console.log("Key(6) found at: " + binarySearchRotated(v1, 6));
let v2 = [4, 5, 6, 1, 2, 3];
console.log("Key(3) found at: " + binarySearchRotated(v2, 3));
console.log("Key(6) found at: " + binarySearchRotated(v2, 6));This solution works iteratively so te algo comes down to O(1) even though the logic remains the same
Next - [[3-SmallestCommonNumber.md]]
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment