# Array problems solved with JavaScript

This article presumes that the reader has a basic knowledge of  [array](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/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 <a href="https://unsplash.com/@asoggetti?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">asoggetti</a> on <a href="https://unsplash.com/t/nature?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>