Mathematiacl Operations

Reverse Integer

Given a signed 32-bit integer, reverse its digits.

String Reversal Approach

Convert the number to string, reverse it, then convert back:

function reverseInteger(x) {
  let result = 0;
  
  if (x >= 0) {
    result = parseInt(String(x).split('').reverse().join(''));
  } else {
    const positive = -x;
    result = -parseInt(String(positive).split('').reverse().join(''));
  }
  
  if (result > Math.pow(2, 31) - 1 || result < -Math.pow(2, 31)) {
    return 0;
  }
  
  return result;
}

Mathematical Approach

Extract digits using modulo and division operations:

function reverseInteger(x) {
  let reversed = 0;
  
  while (x !== 0) {
    reversed = reversed * 10 + (x % 10);
    
    if (reversed > Math.pow(2, 31) - 1 || reversed < -Math.pow(2, 31)) {
      return 0;
    }
    
    x = Math.trunc(x / 10);
  }
  
  return reversed;
}

Roman to Integer

Convert Roman numerals to integers.

Map-Based Solution

function romanToInteger(s) {
  const values = new Map([
    ['I', 1],
    ['V', 5],
    ['X', 10],
    ['L', 50],
    ['C', 100],
    ['D', 500],
    ['M', 1000]
  ]);
  
  let total = 0;
  
  for (let i = 0; i < s.length; i++) {
    const current = values.get(s[i]);
    const next = values.get(s[i + 1]);
    
    if (i < s.length - 1 && current < next) {
      total -= current;
    } else {
      total += current;
    }
  }
  
  return total;
}

Switch Statement Solution

function romanToInteger(s) {
  let total = 0;
  
  for (let i = 0; i < s.length; i++) {
    const currentValue = getRomanValue(s[i]);
    const nextValue = getRomanValue(s[i + 1]);
    
    if (i < s.length - 1 && currentValue < nextValue) {
      total -= currentValue;
    } else {
      total += currentValue;
    }
  }
  
  return total;
}

function getRomanValue(char) {
  switch (char) {
    case 'I': return 1;
    case 'V': return 5;
    case 'X': return 10;
    case 'L': return 50;
    case 'C': return 100;
    case 'D': return 500;
    case 'M': return 1000;
    default: return 0;
  }
}

Power Function

Implement pow(x, n).

Fast Exponentiation

function power(x, n) {
  let result = 1;
  let base = x;
  let exponent = n;
  
  if (exponent < 0) {
    base = 1 / base;
    exponent = -exponent;
  }
  
  while (exponent > 0) {
    if (exponent & 1) {
      result *= base;
    }
    base *= base;
    exponent >>>= 1;
  }
  
  return result;
}

Array Manipulation

Two Sum

Find indices of two numbers that sum to target.

Brute Force

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

Hash Map Solution

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 [];
}

Container With Most Water

Find two lines that form container with maximum area.

function maxArea(height) {
  let left = 0;
  let right = height.length - 1;
  let maxArea = 0;
  
  while (left < right) {
    const currentArea = Math.min(height[left], height[right]) * (right - left);
    maxArea = Math.max(maxArea, currentArea);
    
    if (height[left] <= height[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxArea;
}

Remove Duplicates from Sorted Array

Remove duplicates in-place from sorted array.

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

Remove Element

Remove all instances of specific value from array.

Two Pointer Approach

function removeElement(nums, val) {
  let writeIndex = 0;
  
  for (let readIndex = 0; readIndex < nums.length; readIndex++) {
    if (nums[readIndex] !== val) {
      nums[writeIndex] = nums[readIndex];
      writeIndex++;
    }
  }
  
  return writeIndex;
}

Two Pointer from Both Ends

function removeElement(nums, val) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    if (nums[left] === val) {
      nums[left] = nums[right];
      right--;
    } else {
      left++;
    }
  }
  
  return left;
}

Maximum Subarray

Find contiguous subarray with maximum sum.

function maxSubArray(nums) {
  let currentSum = nums[0];
  let maxSum = 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;
}

Spiral Matrix

Traverse matrix in spiral order.

function spiralOrder(matrix) {
  if (!matrix.length || !matrix[0].length) return [];
  
  const rows = matrix.length;
  const cols = matrix[0].length;
  const result = [];
  
  let top = 0;
  let bottom = rows - 1;
  let left = 0;
  let right = cols - 1;
  
  while (top <= bottom && left <= right) {
    for (let col = left; col <= right; col++) {
      result.push(matrix[top][col]);
    }
    top++;
    
    for (let row = top; row <= bottom; row++) {
      result.push(matrix[row][right]);
    }
    right--;
    
    if (top <= bottom) {
      for (let col = right; col >= left; col--) {
        result.push(matrix[bottom][col]);
      }
      bottom--;
    }
    
    if (left <= right) {
      for (let row = bottom; row >= top; row--) {
        result.push(matrix[row][left]);
      }
      left++;
    }
  }
  
  return result;
}

Sort Colors

Sort array containing 0s, 1s, and 2s representing colors.

function sortColors(nums) {
  let low = 0;
  let high = nums.length - 1;
  
  for (let i = 0; i <= high; i++) {
    if (nums[i] === 0) {
      [nums[i], nums[low]] = [nums[low], nums[i]];
      low++;
    } else if (nums[i] === 2) {
      [nums[i], nums[high]] = [nums[high], nums[i]];
      high--;
      i--;
    }
  }
}

Merge Sorted Array

Merge two sorted arrays into first aray.

function merge(nums1, m, nums2, n) {
  let i = m - 1;
  let j = n - 1;
  let k = m + n - 1;
  
  while (i >= 0 && j >= 0) {
    if (nums1[i] > nums2[j]) {
      nums1[k] = nums1[i];
      i--;
    } else {
      nums1[k] = nums2[j];
      j--;
    }
    k--;
  }
  
  while (j >= 0) {
    nums1[k] = nums2[j];
    j--;
    k--;
  }
}

Best Time to Buy and Sell Stock

Find maximum profit from single transaction.

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;
}

Kth Largest Element

Find kth largest element in unsorted array.

function findKthLargest(nums, k) {
  let left = 0;
  let right = nums.length - 1;
  let target = k - 1;
  
  while (true) {
    const pivotIndex = partition(nums, left, right);
    
    if (pivotIndex === target) {
      return nums[pivotIndex];
    } else if (pivotIndex > target) {
      right = pivotIndex - 1;
    } else {
      left = pivotIndex + 1;
    }
  }
}

function partition(nums, left, right) {
  const pivot = nums[left];
  let j = left;
  
  for (let i = left + 1; i <= right; i++) {
    if (nums[i] > pivot) {
      j++;
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  
  [nums[left], nums[j]] = [nums[j], nums[left]];
  return j;
}

Move Zeroes

Move all zeroes to end while maintaining relative order.

function moveZeroes(nums) {
  let writeIndex = 0;
  
  for (let readIndex = 0; readIndex < nums.length; readIndex++) {
    if (nums[readIndex] !== 0) {
      [nums[writeIndex], nums[readIndex]] = [nums[readIndex], nums[writeIndex]];
      writeIndex++;
    }
  }
}

Binary Search

Search for target in sorted array.

function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;
}

String Operations

Longest Substring Without Repeating Characters

Find length of longest substring with unique characters.

Sliding Window Approach

function lengthOfLongestSubstring(s) {
  let maxLength = 0;
  let left = 0;
  const charSet = new Set();
  
  for (let right = 0; right < s.length; right++) {
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    
    charSet.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

Valid Parentheses

Check if parentheses in string are valid.

function isValid(s) {
  const stack = [];
  const pairs = {
    ')': '(',
    '}': '{',
    ']': '['
  };
  
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    
    if (char === '(' || char === '{' || char === '[') {
      stack.push(char);
    } else if (stack.pop() !== pairs[char]) {
      return false;
    }
  }
  
  return stack.length === 0;
}

Reverse Vowels

Reverse only vowels in string.

function reverseVowels(s) {
  const chars = s.split('');
  const vowels = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']);
  let left = 0;
  let right = s.length - 1;
  
  while (left < right) {
    if (!vowels.has(chars[left])) {
      left++;
      continue;
    }
    
    if (!vowels.has(chars[right])) {
      right--;
      continue;
    }
    
    [chars[left], chars[right]] = [chars[right], chars[left]];
    left++;
    right--;
  }
  
  return chars.join('');
}

Add Strings

Add two numbers represented as strings.

function addStrings(num1, num2) {
  let carry = 0;
  let i = num1.length - 1;
  let j = num2.length - 1;
  const result = [];
  
  while (i >= 0 || j >= 0 || carry > 0) {
    const digit1 = i >= 0 ? parseInt(num1[i]) : 0;
    const digit2 = j >= 0 ? parseInt(num2[j]) : 0;
    
    const sum = digit1 + digit2 + carry;
    result.push(sum % 10);
    carry = Math.floor(sum / 10);
    
    i--;
    j--;
  }
  
  return result.reverse().join('');
}