Data Structure & Algorithms using JavaScript : Arrays

Credits: Unsplash

Two Sum

Brute Force Solution

The brute force approach involves checking all possible pairs of numbers to see if they add up to the target. This approach has a time complexity of O(n²).

function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

Optimised Solution

The optimised solution uses a hash map to store the difference between the target and each number. This way, we can find the solution in one pass with a time complexity of O(n).

function twoSum(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
    return [];
}

Explanation

Brute Force Solution:

• Iterate through each element in the array with two nested loops.
• Check if the sum of any two different elements equals the target.
• If a pair is found, return their indices.

Optimised Solution:

• Create an empty hash map to store the numbers and their indices.
• Iterate through the array:
• For each element, calculate the complement by subtracting the current element from the target.
• Check if the complement exists in the hash map.
• If it does, return the indices of the complement and the current element.
• If not, add the current element and its index to the hash map.

This optimised solution is more efficient and suitable for larger arrays.

Best Time to Buy and Sell Stock

Brute Force Solution

The brute force approach involves checking all possible pairs of buy and sell prices. This approach has a time complexity of O(n²).

function maxProfit(prices) {
    let maxProfit = 0;
    for (let i = 0; i < prices.length; i++) {
        for (let j = i + 1; j < prices.length; j++) {
            let profit = prices[j] - prices[i];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }
    }
    return maxProfit;
}

Optimised Solution

The optimised solution keeps track of the minimum price encountered so far and calculates the potential profit for each price. This way, we can find the solution in one pass with a time complexity of O(n).

function maxProfit(prices) {
    let minPrice = Infinity;
    let maxProfit = 0;
    for (let i = 0; i < prices.length; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }
    return maxProfit;
}

Explanation

Brute Force Solution:

• Iterate through each element in the array with two nested loops.
• Check the profit for every possible pair of buy and sell prices.
• Update the maximum profit if a higher profit is found.

Optimised Solution:

• Initialise minPrice to infinity and maxProfit to 0.
• Iterate through the array:
• Update minPrice to the current price if it is lower than the current minPrice.
• Calculate the potential profit by subtracting minPrice from the current price.
• Update maxProfit if the calculated profit is higher than the current maxProfit.

This optimised solution is more efficient and suitable for larger arrays.

Contains Duplicate

Brute Force Solution

The brute force approach involves checking each pair of elements to see if any two are the same. This approach has a time complexity of O(n²).

function containsDuplicate(nums) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] === nums[j]) {
                return true;
            }
        }
    }
    return false;
}

Optimised Solution

The optimised solution uses a Set to track the elements we have seen so far. This approach has a time complexity of O(n).

function containsDuplicate(nums) {
    const seen = new Set();
    for (let i = 0; i < nums.length; i++) {
        if (seen.has(nums[i])) {
            return true;
        }
        seen.add(nums[i]);
    }
    return false;
}

Explanation

Brute Force Solution:

• Iterate through each element in the array with two nested loops.
• Check if any pair of elements are the same.
• If a pair is found, return true.
• If no pairs are found after checking all elements, return false.

Optimised Solution:

• Create an empty Set to keep track of the elements we have seen.
• Iterate through the array:
• Check if the current element is already in the Set.
• If it is, return true (indicating a duplicate).
• If it is not, add the current element to the Set.
• If no duplicates are found after checking all elements, return false.

This optimised solution is more efficient and suitable for larger arrays.

Product of Array Except Self

Brute Force Solution

The brute force approach involves calculating the product for each element by iterating through the array twice. This approach has a time complexity of O(n²).

function productExceptSelf(nums) {
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        let product = 1;
        for (let j = 0; j < nums.length; j++) {
            if (i !== j) {
                product *= nums[j];
            }
        }
        result.push(product);
    }
    return result;
}

Optimised Solution

The optimised solution uses two additional arrays to store the prefix and suffix products and then combines them to get the desired result. This approach has a time complexity of O(n) and space complexity of O(n).

function productExceptSelf(nums) {
    const length = nums.length;
    const result = new Array(length).fill(1);
    const leftProducts = new Array(length).fill(1);
    const rightProducts = new Array(length).fill(1);

    for (let i = 1; i < length; i++) {
        leftProducts[i] = leftProducts[i - 1] * nums[i - 1];
    }

    for (let i = length - 2; i >= 0; i--) {
        rightProducts[i] = rightProducts[i + 1] * nums[i + 1];
    }

    for (let i = 0; i < length; i++) {
        result[i] = leftProducts[i] * rightProducts[i];
    }

    return result;
}

Further Optimised Solution (O(1) space, excluding the output array)

We can further optimise the space complexity to O(1) by using the result array itself to store the prefix and suffix products.

function productExceptSelf(nums) {
    const length = nums.length;
    const result = new Array(length).fill(1);

    let leftProduct = 1;
    for (let i = 0; i < length; i++) {
        result[i] = leftProduct;
        leftProduct *= nums[i];
    }

    let rightProduct = 1;
    for (let i = length - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }

    return result;
}

Explanation

Brute Force Solution:

• Iterate through each element in the array with two nested loops.
• For each element, calculate the product of all other elements.
• Store the product in the result array.

Optimised Solution:

• Create two auxiliary arrays: leftProducts and rightProducts.
• Calculate the prefix products and store them in leftProducts.
• Calculate the suffix products and store them in rightProducts.
• Combine the prefix and suffix products to get the final result.

Further Optimised Solution:

• Use the result array to store the prefix products in a single pass.
• Update the result array with the suffix products in a single reverse pass.

This further optimised solution is more space-efficient while maintaining the time complexity of O(n).

Maximum Subarray

Brute Force Solution

The brute force approach involves checking all possible subarrays and calculating their sums. This approach has a time complexity of O(n²).

function maxSubArray(nums) {
    let maxSum = nums[0];
    for (let i = 0; i < nums.length; i++) {
        let currentSum = 0;
        for (let j = i; j < nums.length; j++) {
            currentSum += nums[j];
            if (currentSum > maxSum) {
                maxSum = currentSum;
            }
        }
    }
    return maxSum;
}

Optimised Solution

The optimised solution uses Kadane’s Algorithm, which has a time complexity of O(n).

function maxSubArray(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

Explanation

Brute Force Solution:

• Iterate through each possible starting point of the subarray using the outer loop.
• Iterate through each possible ending point of the subarray using the inner loop.
• Calculate the sum of the current subarray and update maxSum if the current sum is greater than the current maxSum.
• Return maxSum after checking all possible subarrays.

Optimised Solution:

• Initialize maxSum and currentSum to the first element of the array.
• Iterate through the array starting from the second element:
• Update currentSum to be the maximum of the current element and the sum of currentSum and the current element.
• Update maxSum to be the maximum of maxSum and currentSum.
• Return maxSum after iterating through the array.

The optimised solution is more efficient and suitable for larger arrays, reducing the time complexity from O(n²) to O(n).

Maximum Product Subarray

Brute Force Solution

The brute force approach involves checking all possible subarrays and calculating their products. This approach has a time complexity of O(n³).

function maxProduct(nums) {
    let maxProduct = nums[0];
    for (let i = 0; i < nums.length; i++) {
        for (let j = i; j < nums.length; j++) {
            let product = 1;
            for (let k = i; k <= j; k++) {
                product *= nums[k];
            }
            maxProduct = Math.max(maxProduct, product);
        }
    }
    return maxProduct;
}

Optimised Solution

The optimised solution uses a dynamic programming approach. It keeps track of the maximum and minimum products up to the current position, which is important because a negative number can become positive when multiplied by another negative number. This approach has a time complexity of O(n).

function maxProduct(nums) {
    let maxProduct = nums[0];
    let currentMax = nums[0];
    let currentMin = nums[0];

    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < 0) {
            [currentMax, currentMin] = [currentMin, currentMax];
        }

        currentMax = Math.max(nums[i], currentMax * nums[i]);
        currentMin = Math.min(nums[i], currentMin * nums[i]);

        maxProduct = Math.max(maxProduct, currentMax);
    }

    return maxProduct;
}

Explanation

Brute Force Solution:

• Iterate through each possible starting point of the subarray using the outer loop.
• Iterate through each possible ending point of the subarray using the middle loop.
• Calculate the product of the current subarray using the innermost loop.
• Update maxProduct if the current product is greater than the current maxProduct.
• Return maxProduct after checking all possible subarrays.

Optimised Solution:

• Initialize maxProduct, currentMax, and currentMin to the first element of the array.
• Iterate through the array starting from the second element:
• If the current element is negative, swap currentMax and currentMin because multiplying by a negative number flips the sign.
• Update currentMax to be the maximum of the current element and the product of currentMax and the current element.
• Update currentMin to be the minimum of the current element and the product of currentMin and the current element.
• Update maxProduct to be the maximum of maxProduct and currentMax.
• Return maxProduct after iterating through the array.

The optimised solution is more efficient and suitable for larger arrays, reducing the time complexity from O(n³) to O(n).

Find Minimum in Rotated Sorted Array

Brute Force Solution

The brute force approach involves iterating through the entire array to find the minimum element. This approach has a time complexity of O(n).

function findMin(nums) {
    let min = nums[0];
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] < min) {
            min = nums[i];
        }
    }
    return min;
}

Optimised Solution

The optimised solution uses binary search to find the minimum element. This approach has a time complexity of O(logn).

function findMin(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);

        // If mid element is greater than the rightmost element,
        // the minimum must be to the right of mid
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    // At the end of the while loop, left == right, which points to the minimum element
    return nums[left];
}

Explanation

Brute Force Solution:

• Initialize the minimum element to the first element of the array.
• Iterate through the array, updating the minimum element whenever a smaller element is found.
• Return the minimum element.

Optimised Solution:

• Initialize two pointers, left and right, to the start and end of the array.
• Use binary search:
• Calculate the middle index mid.
• If the middle element is greater than the rightmost element, the minimum element must be to the right of mid, so update left to mid + 1.
• Otherwise, the minimum element must be to the left of or at mid, so update right to mid.
• Continue the binary search until left equals right, which will point to the minimum element.
• Return the element at the left index.

The optimised solution is more efficient and suitable for larger arrays, reducing the time complexity from O(n) to O(logn).

Search in Rotated Sorted Array

Brute Force Solution

The brute force approach involves iterating through the entire array to find the target element. This approach has a time complexity of O(n).

function search(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) {
            return i;
        }
    }
    return -1;
}

Optimised Solution

The optimised solution uses binary search to find the target element in the rotated sorted array. This approach has a time complexity of O(log⁡n).

function search(nums, target) {
    let left = 0;
    let right = nums.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (nums[mid] === target) {
            return mid;
        }

        // Determine which part is properly sorted
        if (nums[left] <= nums[mid]) {
            // Left part is sorted
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; // Target is in the left part
            } else {
                left = mid + 1; // Target is in the right part
            }
        } else {
            // Right part is sorted
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1; // Target is in the right part
            } else {
                right = mid - 1; // Target is in the left part
            }
        }
    }

    return -1; // Target is not found
}

Explanation

Brute Force Solution:

• Iterate through each element in the array.
• If the current element equals the target, return the index.
• If the target is not found after iterating through the array, return -1.

Optimised Solution:

• Initialize two pointers, left and right, to the start and end of the array.
• Use binary search:
• Calculate the middle index mid.
• If the middle element equals the target, return mid.
• Determine which part of the array is properly sorted:
• If the left part is sorted (nums[left] <= nums[mid]):
• Check if the target is within the range of the sorted left part. If yes, update right to mid - 1.
• If not, update left to mid + 1.
• If the right part is sorted:
• Check if the target is within the range of the sorted right part. If yes, update left to mid + 1.
• If not, update right to mid - 1.
• Continue the binary search until the target is found or the pointers left and right cross.
• If the target is not found, return -1.

The optimised solution is more efficient and suitable for larger arrays, reducing the time complexity from O(n)to O(log⁡n).

3 Sum

Brute Force Solution

The brute force approach involves checking all possible triplets. This approach has a time complexity of O(n³).

function threeSum(nums) {
    const result = [];
    nums.sort((a, b) => a - b); // Sort the array to handle duplicates easily

    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // Skip duplicates

        for (let j = i + 1; j < nums.length - 1; j++) {
            if (j > i + 1 && nums[j] === nums[j - 1]) continue; // Skip duplicates

            for (let k = j + 1; k < nums.length; k++) {
                if (k > j + 1 && nums[k] === nums[k - 1]) continue; // Skip duplicates

                if (nums[i] + nums[j] + nums[k] === 0) {
                    result.push([nums[i], nums[j], nums[k]]);
                }
            }
        }
    }

    return result;
}

Optimised Solution

The optimised solution uses sorting and two pointers to find the triplets. This approach has a time complexity of O(n²).

function threeSum(nums) {
    const result = [];
    nums.sort((a, b) => a - b); // Sort the array to handle duplicates easily

    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue; // Skip duplicates

        let left = i + 1;
        let right = nums.length - 1;

        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];

            if (sum === 0) {
                result.push([nums[i], nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++; // Skip duplicates
                while (left < right && nums[right] === nums[right - 1]) right--; // Skip duplicates
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

Explanation

Brute Force Solution:

• Iterate through each triplet using three nested loops.
• Check if the sum of each triplet is zero.
• Add the triplet to the result if the sum is zero, ensuring no duplicate triplets are added.
• Sort the array at the beginning to easily handle duplicates.

Optimised Solution:

• Sort the array to handle duplicates and make it easier to use the two-pointer technique.
• Iterate through the array with one pointer i.
• Use two additional pointers left and right to find pairs that sum to the negative value of the current element nums[i].
• Move the left pointer to the right and the right pointer to the left to find all possible pairs.
• Skip duplicate elements to avoid adding duplicate triplets to the result.

This optimised solution is more efficient and suitable for larger arrays, reducing the time complexity from O(n³) to O(n²).

Container With Most Water

Brute Force Solution

The brute force approach involves checking the area for all possible pairs of lines. This approach has a time complexity of O(n2).

function maxArea(height) {
    let maxArea = 0;
    for (let i = 0; i < height.length; i++) {
        for (let j = i + 1; j < height.length; j++) {
            const area = Math.min(height[i], height[j]) * (j - i);
            if (area > maxArea) {
                maxArea = area;
            }
        }
    }
    return maxArea;
}

Optimised Solution

The optimised solution uses the two-pointer technique to find the maximum area. This approach has a time complexity of O(n).

function maxArea(height) {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;

    while (left < right) {
        const width = right - left;
        const minHeight = Math.min(height[left], height[right]);
        const area = width * minHeight;
        maxArea = Math.max(maxArea, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxArea;
}

Explanation

Brute Force Solution:

• Iterate through each possible pair of lines using two nested loops.
• For each pair, calculate the area formed by the lines and the x-axis.
• Keep track of the maximum area found.
• Return the maximum area.

Optimised Solution:

• Initialize two pointers, left at the beginning and right at the end of the array.
• Calculate the area formed by the lines at the left and right pointers.
• Move the pointer pointing to the shorter line towards the center to try to find a larger area.
• Repeat until the left pointer crosses the right pointer.
• Keep track of the maximum area found during the iterations.
• Return the maximum area.

The optimised solution is more efficient and suitable for larger arrays, reducing the time complexity from O(n²) to O(n).