LeetCode List — JavaScript Solutions

Solutions

1) Two Sum — Easy

• Problem: Return indices of two numbers that add to target.
• Pattern: HashMap (value → index)
• Complexity: Time O(n), Space O(n)
• Input example: nums=[2,7,11,15], target=9
• Output example: [0,1]

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

---

2) Longest Consecutive Sequence — Medium

• Problem: Longest run of consecutive integers in any order.
• Pattern: Set + grow only from sequence starts
• Complexity: Time O(n), Space O(n)
• Input example: nums=[100,4,200,1,3,2]
• Output example: 4

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (!set.has(x - 1)) {
      let len = 1;
      let y = x;
      while (set.has(y + 1)) {
        y++;
        len++;
      }
      if (len > best) {
        best = len;
      }
    }
  }
  return best;
}

---

3) Longest Substring Without Repeating Characters — Medium

• Problem: Longest substring with all unique chars.
• Pattern: Sliding window with last-seen index
• Complexity: Time O(n), Space O(min(n, alphabet))
• Input example: s=“abcabcbb”
• Output example: 3

function lengthOfLongestSubstring(s) {
  const last = new Map();
  let left = 0;
  let best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (last.has(ch) && last.get(ch) >= left) {
      left = last.get(ch) + 1;
    }
    last.set(ch, right);
    if (right - left + 1 > best) {
      best = right - left + 1;
    }
  }
  return best;
}

---

4) Longest Palindromic Substring — Medium

• Problem: Return the longest palindromic substring.
• Pattern: Expand around centers (odd + even)
• Complexity: Time O(n^2), Space O(1)
• Input example: s=“babad”
• Output example: “bab”

function longestPalindrome(s) {
  if (s.length < 2) {
    return s;
  }
  let start = 0;
  let end = 0;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--;
      r++;
    }
    return [l + 1, r - 1];
  }
  for (let i = 0; i < s.length; i++) {
    const [l1, r1] = expand(i, i);
    const [l2, r2] = expand(i, i + 1);
    if (r1 - l1 > end - start) {
      [start, end] = [l1, r1];
    }
    if (r2 - l2 > end - start) {
      [start, end] = [l2, r2];
    }
  }
  return s.slice(start, end + 1);
}

Optimized: Manacher’s Algorithm — O(n)

• Pattern: Manacher’s (transform with separators + radius array)
• Complexity: Time O(n), Space O(n)
• Input example: s=“babad”
• Output example: “bab”

function longestPalindromeManacher(s) {
  if (s.length <= 1) {
    return s;
  }
  const t = ['^'];
  for (const ch of s) {
    t.push('#');
    t.push(ch);
  }
  t.push('#');
  t.push('$');

  const n = t.length;
  const p = new Array(n).fill(0);
  let center = 0;
  let right = 0;

  for (let i = 1; i < n - 1; i++) {
    const mirror = 2 * center - i;
    if (i < right) {
      p[i] = Math.min(right - i, p[mirror]);
    }
    while (t[i + 1 + p[i]] === t[i - 1 - p[i]]) {
      p[i]++;
    }
    if (i + p[i] > right) {
      center = i;
      right = i + p[i];
    }
  }

  let maxLen = 0;
  let centerIndex = 0;
  for (let i = 1; i < n - 1; i++) {
    if (p[i] > maxLen) {
      maxLen = p[i];
      centerIndex = i;
    }
  }
  const start = Math.floor((centerIndex - maxLen) / 2);
  return s.slice(start, start + maxLen);
}

---

5) Clone Graph — Medium

• Problem: Deep copy an undirected graph.
• Pattern: DFS/BFS with map old→new
• Complexity: Time O(V+E), Space O(V)
• Input example: adjacency=[[2,4],[1,3],[2,4],[1,3]]
• Output example: cloned root with same adjacency (order agnostic)

function cloneGraph(node) {
  if (!node) {
    return null;
  }
  const map = new Map();
  function dfs(n) {
    if (map.has(n)) {
      return map.get(n);
    }
    const copy = { val: n.val, neighbors: [] };
    map.set(n, copy);
    for (const nei of n.neighbors) copy.neighbors.push(dfs(nei));
    return copy;
  }
  return dfs(node);
}

---

6) Graph Valid Tree — Medium

• Problem: Given n and edges, is it a tree?
• Pattern: Union-Find; tree iff edges = n-1 and connected
• Complexity: Time O(n α(n)), Space O(n)
• Input example: n=5, edges=[[0,1],[0,2],[0,3],[1,4]]
• Output example: true

function validTree(n, edges) {
  if (edges.length !== n - 1) {
    return false;
  }
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = Array(n).fill(0);
  function find(x) {
    return parent[x] === x ? x : (parent[x] = find(parent[x]));
  }
  function unite(a, b) {
    a = find(a);
    b = find(b);
    if (a === b) {
      return false;
    }
    if (rank[a] < rank[b]) {
      [a, b] = [b, a];
    }
    parent[b] = a;
    if (rank[a] === rank[b]) {
      rank[a]++;
    }
    return true;
  }
  for (const [u, v] of edges) {
    if (!unite(u, v)) {
      return false;
    }
  }
  return true;
}

---

7) Palindromic Substrings — Medium

• Problem: Count palindromic substrings.
• Pattern: Expand around each center
• Complexity: Time O(n^2), Space O(1)
• Input example: s=“aaa”
• Output example: 6

function countSubstrings(s) {
  let count = 0;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      count++;
      l--;
      r++;
    }
  }
  for (let i = 0; i < s.length; i++) {
    expand(i, i);
    expand(i, i + 1);
  }
  return count;
}

---

8) Container With Most Water — Medium

• Problem: Max area between two vertical lines.
• Pattern: Two pointers from ends
• Complexity: Time O(n), Space O(1)
• Input example: height=[1,8,6,2,5,4,8,3,7]
• Output example: 49

function maxArea(height) {
  let l = 0;
  let r = height.length - 1;
  let best = 0;
  while (l < r) {
    const area = Math.min(height[l], height[r]) * (r - l);
    if (area > best) {
      best = area;
    }
    if (height[l] < height[r]) {
      l++;
    } else {
      r--;
    }
  }
  return best;
}

---

9) Word Break — Medium

• Problem: Can s be segmented by dict words?
• Pattern: DP over prefix; dp[i] = exists j<i with dp[j] && s[j..i) in dict
• Complexity: Time O(n^2), Space O(n)
• Input example: s=“leetcode”, wordDict=[“leet”,“code”]
• Output example: true

function wordBreak(s, wordDict) {
  const set = new Set(wordDict);
  const dp = Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

---

10) Linked List Cycle — Easy

• Problem: Detect cycle in linked list.
• Pattern: Floyd fast/slow pointers
• Complexity: Time O(n), Space O(1)
• Input example: head=[3,2,0,-4], pos=1
• Output example: true

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      return true;
    }
  }
  return false;
}

---

11) Missing Number — Easy

• Problem: Find missing number in [0..n].
• Pattern: XOR (or sum difference)
• Complexity: Time O(n), Space O(1)
• Input example: nums=[3,0,1]
• Output example: 2

function missingNumber(nums) {
  let xor = nums.length;
  for (let i = 0; i < nums.length; i++) {
    xor ^= i ^ nums[i];
  }
  return xor;
}

---

12) 3Sum — Medium

• Problem: Triplets summing to zero, no duplicates.
• Pattern: Sort + two pointers
• Complexity: Time O(n^2), Space O(1) extra (ignoring output)
• Input example: nums=[-1,0,1,2,-1,-4]
• Output example: [[-1,-1,2],[-1,0,1]]

function threeSum(nums) {
  nums.sort((a, b) => a - b);
  const res = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];
      if (sum === 0) {
        res.push([nums[i], nums[l], nums[r]]);
        while (l < r && nums[l] === nums[l + 1]) {
          l++;
        }
        while (l < r && nums[r] === nums[r - 1]) {
          r--;
        }
        l++;
        r--;
      } else if (sum < 0) {
        l++;
      } else {
        r--;
      }
    }
  }
  return res;
}

---

13) Reorder List — Medium

• Problem: L0→L1→…→Ln becomes L0→Ln→L1→Ln-1→…
• Pattern: Find middle, reverse second half, merge
• Complexity: Time O(n), Space O(1)
• Input example: head=[1,2,3,4]
• Output example: [1,4,2,3]

function reorderList(head) {
  if (!head || !head.next) {
    return head;
  }
  // find middle
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // reverse second half
  let prev = null;
  let cur = slow.next;
  slow.next = null;
  while (cur) {
    const nxt = cur.next;
    cur.next = prev;
    prev = cur;
    cur = nxt;
  }
  // merge
  let p1 = head;
  let p2 = prev;
  while (p2) {
    const n1 = p1.next;
    const n2 = p2.next;
    p1.next = p2;
    p2.next = n1;
    p1 = n1;
    p2 = n2;
  }
  return head;
}

---

14) Alien Dictionary — Hard

• Problem: Derive character order from sorted alien words.
• Pattern: Build graph from adjacent word pairs, topo sort (Kahn); validate prefix rule
• Complexity: Time O(total chars), Space O(Σ alphabet)
• Input example: words=[“wrt”,“wrf”,“er”,“ett”,“rftt”]
• Output example: “wertf”

function alienOrder(words) {
  const adj = new Map();
  const indeg = new Map();
  for (const w of words) {
    for (const c of w) {
      if (!adj.has(c)) {
        adj.set(c, new Set());
      }
      if (!indeg.has(c)) {
        indeg.set(c, 0);
      }
    }
  }
  for (let i = 0; i < words.length - 1; i++) {
    const a = words[i];
    const b = words[i + 1];
    if (a.length > b.length && a.startsWith(b)) {
      return '';
    }
    const len = Math.min(a.length, b.length);
    for (let j = 0; j < len; j++) {
      if (a[j] !== b[j]) {
        if (!adj.get(a[j]).has(b[j])) {
          adj.get(a[j]).add(b[j]);
          indeg.set(b[j], (indeg.get(b[j]) || 0) + 1);
        }
        break;
      }
    }
  }
  const q = [];
  for (const [c, d] of indeg) {
    if (d === 0) {
      q.push(c);
    }
  }
  let order = '';
  for (let qi = 0; qi < q.length; qi++) {
    const u = q[qi];
    order += u;
    for (const v of adj.get(u) || []) {
      indeg.set(v, indeg.get(v) - 1);
      if (indeg.get(v) === 0) {
        q.push(v);
      }
    }
  }
  return order.length === indeg.size ? order : '';
}

---

15) Encode and Decode Strings — Medium

• Problem: Encode list of strings to one string and decode back.
• Pattern: Length-prefix encoding
• Complexity: Time O(total length), Space O(total length)
• Input example: strs=[“lint”,“code”,“love”,“you”]
• Output example: encoded=“4#lint4#code4#love3#you”; decoded back to same list

class Codec {
  encode(strs) {
    return strs.map((s) => `${s.length}#${s}`).join('');
  }
  decode(s) {
    const res = [];
    let i = 0;
    while (i < s.length) {
      let j = i;
      while (s[j] !== '#') {
        j++;
      }
      const len = Number(s.slice(i, j));
      const start = j + 1;
      res.push(s.slice(start, start + len));
      i = start + len;
    }
    return res;
  }
}

---

16) Remove Nth Node From End of List — Medium

• Problem: Remove the n-th node from end.
• Pattern: Two pointers with dummy
• Complexity: Time O(n), Space O(1)
• Input example: head=[1,2,3,4,5], n=2
• Output example: [1,2,3,5]

function removeNthFromEnd(head, n) {
  const dummy = { next: head };
  let fast = dummy;
  let slow = dummy;
  for (let i = 0; i < n; i++) {
    fast = fast.next;
  }
  while (fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  slow.next = slow.next.next;
  return dummy.next;
}

---

17) Valid Parentheses — Easy

• Problem: Check if parentheses/brackets are valid.
• Pattern: Stack
• Complexity: Time O(n), Space O(n)
• Input example: s=”()[]{}”
• Output example: true

function isValid(s) {
  const m = { ')': '(', ']': '[', '}': '{' };
  const st = [];
  for (const ch of s) {
    if (m[ch]) {
      if (st.pop() !== m[ch]) {
        return false;
      }
    } else {
      st.push(ch);
    }
  }
  return st.length === 0;
}

---

18) Merge Two Sorted Lists — Easy

• Problem: Merge two increasing lists.
• Pattern: Iterative merge with dummy
• Complexity: Time O(m+n), Space O(1)
• Input example: l1=[1,2,4], l2=[1,3,4]
• Output example: [1,1,2,3,4,4]

function mergeTwoLists(l1, l2) {
  const dummy = { next: null };
  let tail = dummy;
  let a = l1;
  let b = l2;
  while (a && b) {
    if (a.val < b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a || b;
  return dummy.next;
}

---

19) Merge k Sorted Lists — Hard

• Problem: Merge k increasing lists.
• Pattern: Divide & conquer merging (log k rounds)
• Complexity: Time O(N log k), Space O(1) extra
• Input example: lists=[[1,4,5],[1,3,4],[2,6]]
• Output example: [1,1,2,3,4,4,5,6]

function mergeKLists(lists) {
  if (!lists.length) {
    return null;
  }
  function merge(a, b) {
    const dummy = { next: null };
    let t = dummy;
    while (a && b) {
      if (a.val < b.val) {
        t.next = a;
        a = a.next;
      } else {
        t.next = b;
        b = b.next;
      }
      t = t.next;
    }
    t.next = a || b;
    return dummy.next;
  }
  let interval = 1;
  while (interval < lists.length) {
    for (let i = 0; i + interval < lists.length; i += interval * 2) {
      lists[i] = merge(lists[i], lists[i + interval]);
    }
    interval *= 2;
  }
  return lists[0];
}

---

20) Maximum Product Subarray — Medium

• Problem: Max product over contiguous subarray.
• Pattern: Track max/min ending here (handles negatives)
• Complexity: Time O(n), Space O(1)
• Input example: nums=[2,3,-2,4]
• Output example: 6

function maxProduct(nums) {
  let maxHere = nums[0];
  let minHere = nums[0];
  let best = nums[0];
  for (let i = 1; i < nums.length; i++) {
    const x = nums[i];
    const cand1 = x;
    const cand2 = maxHere * x;
    const cand3 = minHere * x;
    maxHere = Math.max(cand1, cand2, cand3);
    minHere = Math.min(cand1, cand2, cand3);
    if (maxHere > best) {
      best = maxHere;
    }
  }
  return best;
}

---

21) Find Minimum in Rotated Sorted Array — Medium

• Problem: Return min in rotated increasing array without duplicates.
• Pattern: Binary search on pivot
• Complexity: Time O(log n), Space O(1)
• Input example: nums=[3,4,5,1,2]
• Output example: 1

function findMin(nums) {
  let l = 0;
  let r = nums.length - 1;
  while (l < r) {
    const m = (l + r) >> 1;
    if (nums[m] > nums[r]) {
      l = m + 1;
    } else {
      r = m;
    }
  }
  return nums[l];
}

---

22) Search in Rotated Sorted Array — Medium

• Problem: Search target in rotated array (distinct values).
• Pattern: Binary search with sorted-half check
• Complexity: Time O(log n), Space O(1)
• Input example: nums=[4,5,6,7,0,1,2], target=0
• Output example: 4

function search(nums, target) {
  let l = 0;
  let r = nums.length - 1;
  while (l <= r) {
    const m = (l + r) >> 1;
    if (nums[m] === target) {
      return m;
    }
    if (nums[l] <= nums[m]) {
      if (nums[l] <= target && target < nums[m]) {
        r = m - 1;
      } else {
        l = m + 1;
      }
    } else {
      if (nums[m] < target && target <= nums[r]) {
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
  }
  return -1;
}