This article presumes that the reader has a basic knowledge of array data structures and how they work in JavaScript. The solutions provided in these article may not be the most optimized at times. Feel free to google and find out more about them. I have tried to provide the output for at least a single test case, to help the reader better understand the problem title.
Choosing the programming language while solving any given problem is entirely up to the user. I have tried not to use inbuilt-methods so as to provide a clear understanding of how the thing actually works.
1. Second largest element in an array
Naive approach:
Traverse the array once and find the position of the largest element in the array. Once, it is found, traverse the array again and check for the next largest element, which is smaller than the element you just found as the largest.
const secondLargest = (arr) => { let res = -1; const largest = getLargest(arr); for (let i = 0; i < arr.length; i++) { if (arr[i] !== arr[largest]) { if (res === -1) { res = i; } else if (arr[i] > arr[res]) { res = i; } } } return res; } const getLargest = (arr) => { let res = 0; for (let i = 0; i < arr.length; i++) { if (arr[i] > arr[res]) { res = i; } } return res; }Results:
FirstInput: [10, 50, 6, 20, 80, 60, 16] Output: 5 SecondInput: [10, 10, 10] Output: -1Optimized approach:
Initialize the first element as the largest and result as -1. Start traversing the array from the second position. If the current element is greater than the largest, change the largest to the current element and the secondLargest to the previous largest. Now if the current element is not equals to the largest element, check whether result is still -1 or the current element is greater than the second largest. If it is greater than the second largest, change the result to the current position.
const secondLargest = (arr) => { let res = -1; let largest = 0; for (let i = 1; i < arr.length; i++) { if (arr[i] > arr[largest]) { res = largest; largest = i; } else if (arr[i] !== arr[largest]) { if (res == -1 || arr[i] > arr[res]) { res = i; } } } return res; }Results:
FirstInput: [10, 50, 6, 20, 80, 60, 16] Output: 5 SecondInput: [10, 10, 10] Output: -1
2. Check if an array is sorted
Solution
const checkIfSorted = (arr) => { let isSorted = true; if (arr.length === 1) { return isSorted; } for (let i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { isSorted = false; } } return isSorted; }Results:
FirstInput: [10, 50, 6, 20, 80, 60, 16] Output: false SecondInput: [10, 10, 10] Output: true ThirdInput: [10, 50, 50, 80, 80, 86, 90] Output: true FourtInput: [20] Output: true
3. Reverse an array
Solution
const reverseArray = (arr) => { for (let i = 0, j = arr.length - 1; i < j; i++, j--) { [arr[i], arr[j]] = [arr[j], arr[i]]; } return arr; }Results:
Input: [10, 50, 6, 20, 80, 60, 16] Output: [16, 60, 80, 20, 6, 5, 50, 10]
4. Remove duplicates inline
Solution
const removeDuplicatesInline = (arr) => { let res = 1; if (arr.length === 0) { return 0; } for (let i = 1; i < arr.length; i++) { if (arr[i] !== arr[res - 1]) { arr[res] = arr[i]; res++; } } return res; }Results:
Input: [10, 20, 20, 30, 30, 46, 46, 46, 50, 50, 51, 52] Output: 7 Input: [] Output: 0
5. Move zeroes to the end
Solution
const moveZeroesToEnd = (arr) => { let count = 0; for (let i = 0; i < arr.length; i++) { if (arr[i] !== 0) { [arr[i], arr[count]] = [arr[count], arr[i]]; count++; } } return arr; }Results:
Input: [10, 5, 0, 0, 8, 0, 9, 0] Output: [10, 5, 8, 9, 0, 0, 0, 0]
6. Left Rotate an array by 1
Solution
const leftRotateByOne = (arr) => { let first = 0, last = arr.length - 1; [arr[first], arr[last]] = [arr[last], arr[first]]; for (let i = 0; i < arr.length - 2; i++) { [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; } return arr; }Results:
Input: [1, 2, 3, 4, 5] Output: [2, 3, 4, 5, 1]
7. Left Rotate an array by N
Solution:
Ѳ(n) time and Ѳ(d) auxilary space
const leftRotate = (arr, d) => { const temp = []; const n = arr.length; for (let i = 0; i < d; i++) { temp[i] = arr[i]; } for (let i = d; i < n; i++) { arr[i - d] = arr[i]; } for (let i = 0; i < d; i++) { arr[n - d + i] = temp[i]; } return arr; }Results:
Input: [1, 2, 3, 4, 5], 2 Output: [3, 4, 5, 1, 2]Reversal Algorithm:
Ѳ(n) time and Ѳ(1) auxilary space
const reverse = (arr, l, h) => { while (l < h) { [arr[l], arr[h]] = [arr[h], arr[l]]; l++; h--; } } const leftRotate = (arr, d) => { reverse(arr, 0, d - 1); reverse(arr, d, arr.length - 1); reverse(arr, 0, arr.length - 1); return arr; }Results:
Input: [1, 2, 3, 4, 5], 2 Output: [3, 4, 5, 1, 2]
8. Leaders in an array
Optimized Solution:
Ѳ(n) time and Ѳ(n) auxilary space
const checkIfSorted = (arr) => { let isSorted = true; if (arr.length === 1) { return isSorted; } for (let i = 1; i < arr.length; i++) { if (arr[i] < arr[i - 1]) { isSorted = false; } } return isSorted; } const reverseArray = (arr) => { for (let i = 0, j = arr.length - 1; i < j; i++, j--) { [arr[i], arr[j]] = [arr[j], arr[i]]; } return arr; } const leadersInArray = (arr) => { const res = []; const n = arr.length; const isSorted = checkIfSorted(arr); if (isSorted) { return [arr[n - 1]]; } let currentLeader = arr[n - 1]; res.push(currentLeader); for (let i = n - 2; i > 0; i--) { if (currentLeader < arr[i]) { currentLeader = arr[i]; res.push(currentLeader); } } return reverseArray(res); }Results:
FirstInput: [1, 3, 5, 10, 5, 8, 6, 4, 2, 1] Output: [10, 8, 6, 4, 2, 1] SecondInput: [10, 20, 30] Output: [30]
9. Maximum difference between elements
Solution:
O(n) time and Ѳ(1) auxilary space
const maximumDifferenceBetweenElements = (arr) => { const n = arr.length; let res = arr[1] - arr[0]; let minValue = arr[0]; for (let i = 1; i < n; i++) { res = Math.max(res, arr[i] - minValue); minValue = Math.min(minValue, arr[i]); } return res; }Results:
FirstInput: [2, 3, 10, 6, 4, 8, 1] Output: 8 SecondInput: [10, 8, 6, 2] Output: -2
10. Stock Buy and Sell Problem - Find max profit
Solution
const stockBuyAndSell = (arr) => { const n = arr.length; let profit = 0; for (let i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { profit += arr[i] - arr[i - 1]; } } return profit; }Results:
Input: [1, 5, 3, 8, 12] Output: 13
11. Stock Buy and Sell Problem - Find days on which user should buy and sell
Solution
const stockBuyAndSell = (arr) => { const n = arr.length; const res = []; for (let i = 1; i < n; i++) { if (arr[i] > arr[i - 1]) { res.push({BuyOn: arr[i - 1], SellOn: arr[i]}); } } return res; }
12. Trapping Rain Water Problem
Solution
const trappingRainWater = (arr) => { const n = arr.length; const leftMax = []; const rightMax = []; let res = 0; leftMax[0] = arr[0]; rightMax[n - 1] = arr[n - 1]; for (let i = 1; i < n; i++) { leftMax[i] = Math.max(leftMax[i - 1], arr[i]); } for (let i = n - 2; i > 0; i--) { rightMax[i] = Math.max(rightMax[i + 1], arr[i]); } for (let i = 1; i < n - 1; i++) { res += Math.min(leftMax[i], rightMax[i]) - arr[i]; } return res; }Results:
Input: [5, 0, 6, 2, 3] Output: 6
13. Find number of consecutive ones in a binary array
Solution:
O(n) time and O(1) auxilary space
const countConsecutiveOnes = (arr) => { const n = arr.length; let currentCount = 0; let res = 0; for (let i = 0; i < n; i++) { if (arr[i] === 0) { currentCount = 0; } else { currentCount++; res = Math.max(res, currentCount); } } return res; }Results:
Input: [1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0 ,1] Output: 4
14. Find the maximum sum of a sub-array in a given array
Solution
O(n) time complexity
const maximumSumInSubArray = (arr) => { const n = arr.length; const maxEnding = []; let res = arr[0]; maxEnding[0] = arr[0]; for (let i = 1; i < n; i++) { maxEnding[i] = Math.max(maxEnding[i - 1] + arr[i], arr[i]); res = Math.max(res, maxEnding[i]); } return res; }Results:
Input: [2, 3, -8, 7, -1, 2, 3] Output: 11
15. Find maximum length of an even-odd sub-array in a given array
Solution
const maxLengthEvenOddSubArray = (arr) => { const n = arr.length; let res = 1; let currentMax = 1; for (let i = 1; i < n; i++) { if ((arr[i] % 2 === 0 && arr[i - 1] % 2 !== 0) || (arr[i] % 2 !== 0 && arr[i - 1] % 2 === 0)) { currentMax++; res = Math.max(res, currentMax); } else { currentMax = 1; } } return res; }Results:
Input: [5, 10, 20, 6, 3, 8] Output: 3
16. Majority element in a given array
Solution
const majorityElement = (arr) => { const n = arr.length; let count = 1, res = 0; for (let i = 1; i < n; i++) { if (arr[i] === arr[res]) { count++; } else { count--; } if (count === 0) { count = 1; res = i; } } count = 0; for (let i = 0; i < n; i++) { if (arr[i] === arr[res]) { count++; } } if (count <= n/2) { res = -1; } return arr[res]; }Results:
Input: [8, 7, 6, 8, 6, 6, 6, 6] Output: 6
17. Minimum group flips in binary array
Solution:
const minimumGroupFlips = (arr) => { const n = arr.length; const res = []; for (let i = 1; i < n; i++) { if (arr[i] !== arr[i - 1]) { if (arr[i] !== arr[0]) { res.push({Start: i}); } else { res.push({End: i - 1}); } } } if (arr[n - 1] !== arr[0]) { res.push({End: n - 1}); } return res; }
Have a great day. Thanks for reading the entire thing.