Array problems solved with JavaScript

Array problems solved with JavaScript

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: -1
    
  • Optimized 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.

Photo by asoggetti on Unsplash