Difficulty
Easy

Longest Common Prefix (opens in a new tab)

  • The main function iteratively updates the common prefix by comparing it with each string in the array.
  • The getCommonPrefix function constructs the common prefix by comparing characters one by one until a mismatch occurs.
/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let i =0;
    if(strs.length===1)
        return strs[0];
    let result ="";
     result += getCommonPrefix(strs[0], strs[1]);
    for(let i=2;i<strs.length;i++){
       result= getCommonPrefix(result, strs[i]);
    }
    return result;
};
 
function getCommonPrefix(str1, str2){
    let longStr;
    let smallStr;
    let result="";
    if(str1[0] !== str2[0])
        return "";
   if(str1.length<=str2.length){
       longStr = str2;
       smallStr = str1;
   }
    else{
        longStr = str1;
       smallStr = str2;
    }
   for(let i=0;i<smallStr.length;i++){
       if(longStr[i]=== smallStr[i]){
           result+=longStr[i];
       }
       else{
           return result;
       }
    } 
    return result;
}
Complexity
  • Time: O(N * M)
    • Where N is the number of strings and M is the length of the shortest string among all the strings.
  • Space: O(M)
    • Where M is the length of the shortest string among all the strings.

Reverse Linked List (opens in a new tab)

  • Iterating through the list and reversing the direction of the next pointers of the nodes.
  • After the entire list is reversed, the head pointer is updated to point to the new head of the list, which was the original tail.
/**
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let prev = null,curr=head,next=null
    while(curr!=null){
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    head = prev;
    return head;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Valid Anagram (opens in a new tab)

  • Create an object called "count" , with key as character of string and value as count of that character in the string
  • Loop through those two strings , one with increasing of count and other with decreasing of count
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
 
var isAnagram = function(s, t) {
    if(s.length !== t.length)
        return false;
    
    let count={};
 
    for(let char of s){
        count[char] = (count[char] || 0) + 1;
    }
    
    for(let char of t){
        if(!count[char])
            return false;
         count[char]--;
    }
    return true;
};
Complexity
  • Time: O(n)
  • Space:
    • O(1) : If the character set is fixed (e.g., ASCII), the space required for the count object is O(1) since the number of unique characters is constant (256 for extended ASCII).
    • O(k) : For Unicode or larger character sets, the space required could be O(k), where k is the number of unique characters in the input.

How Many Numbers Are Smaller Than the Current Number (opens in a new tab)

  • Build a count array to store the frequency of each number
  • Calculate the number of elements lesser than the current number
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function (nums) {
  const length = nums.length;
  const limit = 100;
  let countArray = new Array(limit + 1).fill(0);
 
  // build the count array
  for (let i = 0; i < length; i++) {
    countArray[nums[i]]++;
  }
 
  // calculate the number of elements lesser than the current number in one pass
  let prevCount = 0;
  for (let i = 0; i <= limit; i++) {
    if (countArray[i]) {
      const currentCount = countArray[i];
      countArray[i] = prevCount;
      prevCount += currentCount;
    }
  }
 
  const smallerArray = [];
  for (let i = 0; i < length; i++) {
    smallerArray.push(countArray[nums[i]]);
  }
 
  return smallerArray;
};
Complexity
  • Time: O(n)
  • Space: O(n)

Valid Perfect Square (opens in a new tab)

  • Naive approach would be start half the number now multiply each number by itself and check if it match with target
  • As the array is already sorted Binary search can be modified to reduce the time complexity
/**
 * @param {number} num
 * @return {boolean}
 */
var validPerfectSquare = function (num) {
  if (num == 1) return true;
 
  let left = 0,
    right = Math.floor(num / 2);
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (mid * mid === num) {
      return true;
    }
 
    if (mid * mid < num) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return false;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Search Insert Position (opens in a new tab)

  • Naive approach would be start from left side of the array and insert at a point where you find the first match or next higher number. This approach works very well for small arrays.
  • As the array is already sorted Binary search can be modified to reduce the time complexity
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
  let left = 0, right = nums.length - 1;
  let ans = nums.length;
 
  if (target > nums.at(-1)) {
    // if target is greater than the last element
    return ans;
  }
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2); // obtain the mid value
 
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] >= target) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return ans;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Find Smallest Letter Greater Than Target (opens in a new tab)

  • Binary search technique is used to find the smallest letter greater than the target
  • If the target is greater than the last element or smaller than the first element, return the first element
/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function (letters, target) {
  let left = 0, right = letters.length - 1;
  let ans = 0;
 
  // if target is beyond the limits of letters
  if (target < letters[0] || letters.at(-1) < target) {
    return letters[ans];
  }
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
 
    if (target < letters[mid]) {
      ans = mid;
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
 
  return letters[ans];
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Rotate String (opens in a new tab)

  • check the input "goal" is contained in the concatination of the input "s" with itself and the both input length should same
/**
 * @param {string} s
 * @param {string} goal
 * @return {boolean}
 */
var rotateString = function (s, goal) {
  return s === goal || (s + s).includes(goal) && s.length === goal.length;
};
Complexity
  • Time: O(n)
  • Space: O(n)

Sqrt(x) (opens in a new tab)

  • Use binary search technique to with a range from 0 to x
  • Use the mid value to check if mid * mid is less than or equal to x
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  let left = 0, right = x, ans;
 
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const square = mid * mid;
 
    if (square <= x) {
      ans = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return ans;
};
Complexity
  • Time: O(log(n))
  • Space: O(1)

Pascal's Triangle (opens in a new tab)

  • Start with a pascal 2D array with default array with value 1. Use nested loops; one for row generation and other for values inside the each row.
  • Let each value of the current row be calculated from previous row values excluding 1st and last element. Prepend and append 1 to each row value (pattern says by default)
/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  var pascal = [[1]];
 
  for (var i = 1; i < numRows; i++) {
    pascal[i] = [1]; // 1st element of all the rows is 1
 
    for (var j = 1; j < i; j++) {
      pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j];
    }
 
    pascal[i][i] = 1; // last element of all the rows is 1
  }
  return pascal;
};
Complexity
  • Time: O(n2)
  • Space: O(n2)

Check if Array Is Sorted and Rotated (opens in a new tab)

  • In a sorted array, if current value is greater than the next value, then it is unsorted pair
  • In a rotated sorted array, there will be only at max one unsorted pair
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var check = function (nums) {
  let unsortedCount = 0;
 
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] > nums[(i + 1) % nums.length]) {
      unsortedCount++;
    }
 
    if (unsortedCount > 1) {
      return false;
    }
  }
 
  return true;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Matrix Diagonal Sum (opens in a new tab)

  • The diagonal sum of matrix can be calculated by calculating the sum of the each diagonal and adding up
  • In case the matrix is having odd number of rows, then central element has to be considered only once
/**
 * @param {number[][]} mat
 * @return {number}
 */
var diagonalSum = function (mat) {
  const n = mat.length;
  let diagonalSum = 0;
 
  // sum of diagonal from [0, 0] to [n-1, n-1]
  for (let i = 0; i < n; i++) {
    diagonalSum += mat[i][i];
  }
 
  // sum of diagonal from [0, n-1] to [n-1, 0]
  for (let i = 0, j = n - 1; i < n; i++, j--) {
    diagonalSum += mat[i][j];
  }
 
  // if n is odd, then subtract the central element
  if (n % 2 === 1) {
    diagonalSum -= mat[Math.floor(n / 2)][Math.floor(n / 2)];
  }
 
  return diagonalSum;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Check if Number Has Equal Digit Count and Digit Value (opens in a new tab)

  • Store the count of each digit in the array
  • Compare the count of each digit with the digit value
function digitCount(num) {
  const numCount = new Array(10).fill(0);
 
  for (const digit of num) {
    numCount[digit]++;
  }
 
  for (let idx = 0; idx < num.length; idx++) {
    // if count of digit is not equal to digit value
    if (numCount[idx] != num[idx]) {
      return false;
    }
  }
 
  return true;
}
Complexity
  • Time: O(n)
  • Space: O(1)

Sum of Unique Elements (opens in a new tab)

  • This is basically calculating the frequency of each element and sum up the unique elements (having frequency 1)
/**
 * @param {number[]} nums
 * @return {number}
 */
var sumOfUnique = function (nums) {
  let arr = [],
    sum = 0;
  for (let i = 0; i < nums.length; i++) {
    arr[nums[i]] = (arr[nums[i]] || 0) + 1;
  }
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == 1) {
      sum += i;
    }
  }
  return sum;
};
Complexity
  • Time: O(n)
  • Space: O(n)

Move Zeroes (opens in a new tab)

  • Move all non-zero elements to the front of the array
  • Fill the remaining elements with zeros
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let pointer = 0;
 
  for (let i = 0; i < nums.length; i++) {
    if (nums[i]) {
      nums[pointer] = nums[i];
      pointer++;
    }
  }
 
  for (let i = pointer; i < nums.length; i++) {
    nums[i] = 0;
  }
 
  return nums;
};
Complexity
  • Time: O(n)
  • Space: O(1)

Rotate Array (opens in a new tab)

  • Reverse the entire array to get the correct order of the elements
  • Reverse the first k elements and the remaining elements separately
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  k = k % nums.length;
 
  nums.reverse();
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
  return nums;
};
 
function reverse(nums, start, end) {
  while (start < end) {
    // Swap the start and end elements
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
 
    start++;
    end--;
  }
}
Complexity
  • Time: O(n)
  • Space: O(1)

Longest Harmonious Subsequence (opens in a new tab)

  • Find the frequency of each element
  • if map[key - 1] exist, then calculate max from maxLength,map previousvalue and current value
/**
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function (nums) {
  let map = {};
  for (let i of nums) {
    map[i] = (map[i] || 0) + 1;
  }
  let maxResultLength = 0;
  for (let [key, value] of Object.entries(map)) {
    if (map[key - 1]) {
      maxResultLength = Math.max(maxResultLength, map[key - 1] + value);
    }
  }
  return maxResultLength;
};
Complexity
  • Time: O(n)
  • Space: O(n)

Largest Odd Number in String (opens in a new tab)

  • Find the lastOddNum in string and slice the string from 0 to lastOddNum index
/**
 * @param {string} num
 * @return {string}
 */
var largestOddNumber = function(num) {
    if(num & 1)
        return num;
    let lastOddNum = getLastOddNum(num);
    if(num.length>1){
        let i = num.lastIndexOf(lastOddNum)
        return num.slice(0,i+1);
    }
    return "";
};
 
function getLastOddNum(num){
    for(let i=num.length-1;i>=0;i--){
      if(num[i] & 1 === 1)
          return num[i];
    }
}
Complexity
  • Time: O(n)
  • Space: O(n)

Valid Palindrome (opens in a new tab)

  • The program cleans the input string by keeping only alphanumeric characters and converting them to lowercase.
  • It then checks if the cleaned string is equal to its reverse to determine if it is a palindrome.
/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
  let cleanedStr = '';
 
  // Helper function to check if a character is alphanumeric
  function isAlphanumeric(char) {
    return /^[a-zA-Z0-9]+$/.test(char);
  }
 
  // Build the cleaned string with only alphanumeric characters
  for (let char of s) {
    if (isAlphanumeric(char)) {
      cleanedStr += char.toLowerCase();
    }
  }
 
  // Compare the cleaned string with its reverse
  let reversedStr = cleanedStr.split('').reverse().join('');
  return cleanedStr === reversedStr;
};
Complexity
  • Time: O(n)
  • Space: O(n)

Longest Palindrome (opens in a new tab)

  • The program counts the frequency of each character in the input string s and calculates the length of the longest palindrome that can be formed using those characters.
  • It adds 2 to the length for every pair of characters and includes a central character if the original string length is greater than the count of pairs.
/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
  let longestCount = 0;
  let charCountObj = {};
 
    for (const char of s) {
        charCountObj[char] = (charCountObj[char] || 0) + 1;
        if (charCountObj[char] % 2 == 0) longestCount += 2;
    }
    return s.length > longestCount ? longestCount + 1 : longestCount;
};
Complexity
  • Time: O(n)
  • Space: O(n)
Very easyMedium