DEV Community

Mohmed Ishak
Mohmed Ishak

Posted on

2 Data Structures & Algorithms Questions in JavaScript You Should Know Off The Top Of Your Head

Hey JavaScript engineers! I've selected 2 popular data structures and algorithms questions in JavaScript and written great solutions to solve them with optimal time and space complexity. Do check them out and exercise your JavaScript mind. Don't forget to leave a like.

[1] Finding Palindrome

A palindrome is a word where it is written the same way frontward and backward such as "madam" or "racecar". How do you find a palindrome in JavaScript using optimal time and space complexity?

function isPalindrome(word) {
    let left = 0;
    let right = string.length - 1;

    while (left < right) {
        if (word[left] !== word[right]) return false;
        left++;
        right--;
    }

    return true;
}
Enter fullscreen mode Exit fullscreen mode

Explanation: start with 2 pointers which would point to the very beginning and end of string. Sequentially move them inwards, 1 step at a time until they reach the middle. In every iteration, check whether they are equal.
Time Complexity: O(n) because with more characters in words, the algorithm would take more time to run linearly.
Space Complexity: O(1) because there is a constant need of space (2 pointers) at any given point of this algorithm.

[2] Binary Search

Binary search is a very quick searching algorithm where you divide the elements to be searched by 2 (and ignore 1 half) in every iteration. Don't underestimate the power of dividing something in half or multiplying something by 2. Do you know that if you take 1 cent (1 penny), multiply it by 2, and repeat this process for 30 days, you would get 5 million by the end of the month? The same if true backwards, which is what happens in a binary search algorithm. This means that the algorithm runs very fast as it divides the elements to be searched by 2 in every round. Here's how to do it in JavaScript.

function binarySearch(array, target) {
    return binarySearchAlgorithm(array, target, 0, array.length - 1);
}

function binarySearchAlgorithm(array, target, left, right) {
    if (left > right) return -1;

    let middle = Math.floor((left + right) / 2);
    const current = array[middle];

    if (target == current) return middle;
    else if (target < current) return binarySearchAlgorithm(array, target, left, middle - 1);
    else return binarySearchAlgorithm(array, target, middle + 1, right);
}
Enter fullscreen mode Exit fullscreen mode

Explanation: In this case, I assumed the array is sorted. If it isn't sorted, you should sort it first for this algorithm to work. Start with 2 pointers which would point to very beginning and end of array. Based on these 2 pointers, find the middle element and check whether it is the needed element. If no "restart" this algorithm with smarter decision where you change the pointers and essentially choose whether to check the first half or second half of the array (one half is selected and the other is ignored). Repeat this process until you find the element.
Time Complexity: O(log(n)) as half of the elements are disregarded in every round.
Space Complexity: O(log(n)) as half of the elements are added to the call stack in every round.

Discussion (0)