LeetCode problems

From NoskeWiki
Jump to navigation Jump to search

Contents

About

NOTE: This page is a daughter page of: Programming questions


LeetCode (leetcode.com) is a digital platform that specializes in delivering coding exercises and interview prep materials for software professionals and aspiring developers. It features a variety of coding problems and algorithmic challenges designed for hands-on coding practice. The platform has become a go-to resource for individuals preparing for technical interviews and participating in coding contests.

Their sets of problems are excellent and interactive - you code the solution in their UI and hit run to see if it passes test cases. On this page, I've typed out some solutions.

DISCLAIMER: I only had time to solve a few of the many problems, and not all will be optimal. If you want optimal I suggest you pay for a LeetCode subscription *or* simply ask ChatGPT and 9/10 it will produce an optimal working solution. I checked in some cases and even when I was close to optimal, ChatGPT inspired me to reduce code lines.


LeetCode Problem Set - Top Interview 150 - Solved in Python

These are the "Top Interview 150" questions with some answers. I think I finished about 55% of them (83/150) - maybe one day I'll get time and reason to finish the others.


Array / String


(88) Merge Sorted Array (Easy) Solved

(view problem)

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.


Example:

  • Input:
    nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
  • Output:
    [1,2,2,3,5,6]


Solution
class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        if m == 0 and n > 0:
          for i, num2 in enumerate(nums2):
            nums1[i] = num2
          return

        i = len(nums1) - 1  # End of nums1 where we move next biggest value.
        i1 = m - 1
        i2 = n - 1
        while i >= 0:
          # print('i=', i)
          if i2 < 0:
            return
          if i1 < 0:
            for x in range(0, i2 + 1):
              nums1[x] = nums2[x]
            return
          if nums2[i2] >= nums1[i1]:
            nums1[i] = nums2[i2]
            i2 -= 1
          else:
            nums1[i] = nums1[i1]
            i1 -= 1
          i -= 1




(27) Remove Element (Easy) Solved

(view problem)

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums that are not equal to val.

Consider the number of elements in nums that are not equal to val be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.


Example:

  • Input:
    nums = [3,2,2,3], val = 3
  • Output:
    2, nums = [2,2,_,_]


Solution
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = len(nums) - 1
        end = i
        while i >= 0:
          curr_val = nums[i]
          if curr_val == val:
            if end != i:
              # Swap:
              nums[i], nums[end] = nums[end], nums[i]
            end -= 1
            nums.pop()            
          i -= 1




(26) Remove Duplicates from Sorted Array (Easy) Solved (+)

(view problem)

Given an integer array nums sorted in non-decreasing order, remove the duplicates in place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.


Example:

  • Input:
    nums = [1,1,2]
  • Output:
    output = [1,2,_]


Solution
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        unique_idx = 0
        for i in range(1, len(nums)):
            if nums[i] != nums[unique_idx]:
                unique_idx += 1
            if i != unique_idx:
                nums[unique_idx] = nums[i]
        nums = nums[0:unique_idx]
        return unique_idx + 1
C++ Solution
class Solution {
public:
    // [1,2,2,3,3,3,4] -> [1,2,3,4]
    //      *
    // [1,1,2] -> [1,2]
    //    ^ 
    // unique_idx = 0; i = 0

    int removeDuplicates(vector<int>& nums) {
      int unique_idx = 0;
      for(int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[unique_idx]) {
            unique_idx++;
        }
        if (i != unique_idx) {
            nums[unique_idx] = nums[i];
        }
      }
      nums.resize(unique_idx + 1);
      return unique_idx + 1;
    }
};



(80) Remove Duplicates from Sorted Array II (Medium) Solved

(view problem)

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative order of the elements should be kept the same.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.


Example:

  • Input:
    nums = [1,1,1,2,2,3]
  • Output:
    5, nums = [1,1,2,2,3,_]


Solution
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) <= 2:
            return len(nums)
        fixed_idx = 2  # Last index of corrected array.
        for i in range(2, len(nums)):
            if nums[i] == nums[fixed_idx-2]:
                continue
            else:
                nums[fixed_idx] = nums[i]
                fixed_idx += 1
        return fixed_idx




(169) Majority Element (Easy) Solved (+)

(view problem)

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.


Example:

  • Input:
    nums = [3,2,3]
  • Output:
    3


Solution
class Solution(object):
    def majorityElement(self, nums):
        # Edge cases:
        if len(nums) == 1:
            return nums[0]
        # Normal case:
        nums.sort()
        occurances = 1
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                occurances += 1
                if occurances >= len(nums) / 2:
                    return nums[i]
            else:
                occurance = 1
        return -1  # No majority case
The Boyer-Moore Voting Algorithm Trick
# Boyer-Moore Voting Algorithm Trick:
# 1. Maintain a count of our current candidate for majority element.
# 2. Iterate through the list, and for each number:
#    - If our count is 0: set current candidate to the current number.
#    - If number is our current candidate: increment count.
#    - If number is not current candidate: decrement count.
# 3. Given that a majority element exists in the array, our
#    candidate will eventually be the majority element.
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate, count = nums[0], 1
        for num in nums[1:]:
            if count == 0:  # We have a new candidate.
                candidate = num
                count = 1
            elif candidate == num:
                count += 1
            else:
                count -= 1
        return candidate



(189) Rotate Array (Medium) Solved

(view problem)

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.


Example:

  • Input:
    nums = [1,2,3,4,5,6,7], k = 3
  • Output:
    [5,6,7,1,2,3,4]


Solution
Uses a "reversing" trick.
void reverse_array_range(vector<int>& nums, int start, int end) {
    int swap_range = (end + 1 - start) / 2;
    for (int i = 0; i < swap_range; i++) {
        std::swap(nums[start + i], nums[end - i]);
    }
}

class Solution {
public:
    // Example: nums = [1,2,3,4,5,6,7], k = 3 -> [5,6,7,1,2,3,4]
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        if (k == 0) {
            return;
        }
        // Perform reversing trick:
        reverse_array_range(nums, 0, n - 1);
        reverse_array_range(nums, 0, k - 1);
        reverse_array_range(nums, k, n - 1);
    }
};




(121) Best Time to Buy and Sell Stock (Easy) Solved

(view problem)

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.


Example:

  • Input:
    prices = [7,1,5,3,6,4]
  • Output:
    5


Solution
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # Buy lowest, sell highest.
        curr_max = -sys.maxsize
        curr_min = sys.maxsize
        biggest_gain = -sys.maxsize
        # prices = [7,1,5,3,6,4] -> 5 (6-1)
        for price in prices:
            if price < curr_min:
                curr_min = price
                curr_max = price
            curr_max = max(curr_max, price)
            biggest_gain = max(biggest_gain, curr_max - curr_min)
        return biggest_gain




(122) Best Time to Buy and Sell Stock II (Medium) Solved

(view problem)

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.


Example:

  • Input:
    prices = [7,1,5,3,6,4]
  • Output:
    7


Solution
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0

        # Buy low, sell high - always sell before a drop (easy).
        total_profit = 0  # Running total profit.
        for i in range(1, len(prices)):
            profit = prices[i] - prices[i-1]
            if profit > 0:
                total_profit += profit
        return total_profit




(55) Jump Game (Medium) Solved

(view problem)

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.


Example:

  • Input:
    nums = [2,3,1,1,4]
  • Output:
    true


Solution
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        if len(nums) == 0:
            return False
        if len(nums) == 1:  # TODO(noske): Try remove.
            return True
        # [2,3,1,1,4] -> true.   idx: 0 > 1 > last.
        # [3,2,1,0,4] -> false.  cannot get past idx 3.
        reachable = [False] * len(nums)
        reachable[0] = True
        for i in range(len(nums)):
            if not reachable[i]:
                return False
            jump = nums[i]
            for j in range(i+1, i+1+jump):
                # TODO: Optimize: should start from end return when true
                # as app prior cells will already be true.
                reachable[j] = True
                if j == len(reachable) - 1:
                    return True
        return reachable[len(reachable) - 1]




(45) Jump Game II (Medium) Solved

(view problem)

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

0 <= j <= nums[i] and i + j < n Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].


Example:

  • Input:
    nums = [2,3,1,1,4]
  • Output:
    2


Solution
MAX_INT = 9000  # sys.maxsize

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return 0
        # [2,3,1,1,4] -> 2   .... from idx 0->1 ... 1->last
        min_jumps = [MAX_INT] * len(nums)
        min_jumps[0] = 0
        for i in range(len(nums) - 1):
            jump_range = nums[i]
            new_min_jump = min_jumps[i] + 1
            for j in range(i+1, min(i+1+jump_range, len(min_jumps))):
                min_jumps[j] = min(min_jumps[j], new_min_jump)
        return min_jumps[-1]
Greedy Approach With Better Runtime
# The problem can be solved more efficiently using a greedy algorithm.
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n <= 1:
            return 0
        jumps = 0
        current_jump_end = 0
        farthest = 0
        for i in range(n - 1):  # We don't need to jump from the last position.
            # Always try to jump as far as possible
            farthest = max(farthest, i + nums[i])
            # If we've come to the end of the current jump, 
            # increment our jump count and update our endpoint
            if i == current_jump_end:
                jumps += 1
                current_jump_end = farthest
                # If farthest has already reached or exceeded the last index
                if farthest >= n - 1:
                    break
        return jumps



(274) H-Index (Medium) Solved

(view problem)

Given an array of integers citations where citations[i] is the number of citations a researcher received for their ith paper, return the researcher's h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.


Example:

  • Input:
    citations = [3,0,6,1,5]
  • Output:
    3


Solution
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        if not citations:
            return 0
        num_papers = len(citations)
        citation_freq = [0] * (num_papers + 1)
        for x in citations:
            if x == 0:
                continue
            if x > num_papers:
                x = num_papers
            citation_freq[x] += 1
        prev_freq = 0
        for x in range(num_papers, -1, -1):
            citation_freq[x] += prev_freq
            if citation_freq[x] >= x:
                return x
            prev_freq = citation_freq[x]
        return 0
No Extra Storage Solution
To solve this problem in good runtime without extra storage, we can sort the citations array and then linearly search for the h-index. The idea is to leverage the sorted order to efficiently determine the number of papers that have at least i citations.
class Solution:
    def hIndex(self, citations: List[int]) -> int:
        citations.sort(reverse=True)
        h = 0
        for i, citation in enumerate(citations):
            if citation >= i + 1:
                h = i + 1
            else:
                break
        return h



(380) Insert Delete GetRandom O(1) (Medium) Solved

(view problem)

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.


Example:

  • Input:
    ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]

[[], [1], [2], [2], [], [1], [2], []]

  • Output:
    [null, true, false, true, 2, true, false, 2]


Solution
import random

class RandomizedSet:

    def __init__(self):
        self.my_set = set()
        self.my_array = []

    def insert(self, val: int) -> bool:
        if val in self.my_set:
            return False
        self.my_set.add(val)
        self.my_array.append(val)
        return True

    def remove(self, val: int) -> bool:
        if not val in self.my_set:
            return False
        self.my_set.remove(val)
        self.my_array.remove(val)
        return True

    def getRandom(self) -> int:
        return random.choice(self.my_array)


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()




(238) Product of Array Except Self (Medium) Solved

(view problem)

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.


Example:

  • Input:
    nums = [-1,1,0,-3,3]
  • Output:
    [0,0,9,0,0]


Example:

  • Input:
    nums =[1,2,3,4]
  • Output:
    [24,12,8,6]


Solution
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        if not nums:
            return []
        new_array = [0] * len(nums)
        # Calculate total product:
        total_product = 1
        num_zeros = 0
        for num in nums:
            if num != 0:
                total_product *= num
            else:
                num_zeros += 1
                if num_zeros > 1:  # If two zeros, everything will be 0.
                    return new_array

        for i, num in enumerate(nums):
            if num == 0:
                if num_zeros == 1:  # For [1, 0, 3] case.
                    new_array[i] = total_product
            else:
                if num_zeros == 0:  # For [1, 2, 3] case.
                    new_array[i] = int(total_product // num)
        return new_array




(134) Gas Station (Medium) Medium

(view problem)

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.


Example:

  • Input:
    gas = [1,2,3,4,5], cost = [3,4,5,1,2]
  • Output:
    3


Solution
class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # Sanity check:
        if len(gas) != len(cost):
            return -1

        STATIONS = len(gas)
        tank = 0
        start_idx = 0
        for i in range(STATIONS * 2):
            if tank < 0:  # Last section was net loss.
                start_idx = i
                tank = 0
            tank += gas[i % STATIONS] - cost[i % STATIONS]
            if i >= start_idx + STATIONS:
                return (i % STATIONS)
        return -1




(135) Candy (Hard) Solved

(view problem)

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.


Example:

  • Input:
    ratings = [1,0,2]
  • Output:
    5


Solution
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        # Every child should have at least one candy:
        candies = [1] * n
        # Traverse the ratings from left to right:
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        # Traverse the ratings from right to left:
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
                candies[i] = candies[i + 1] + 1
        return sum(candies)




(42) Trapping Rain Water (Hard) Complete

(view problem)

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.


Example:

  • Input:
    height = [0,1,0,2,1,0,1,3,2,1,2,1]
  • Output:
    6


Solution
# Spoiler... this approach is not optimal - it's overkill.
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n <= 2:
            return 0
        filled = [False] * n  # If this block was filled over.

        # 2D array with heights (to sort on) and x position (index in height).
        sorted_heights = []
        for x, y in enumerate(height):
            sorted_heights.append((y, x))
        # Create one version prioritizing furthest right blocks,
        # and the other furthest left:
        sorted_heights = sorted(sorted_heights, key = lambda x: (x[0], x[1]), reverse=True)
        sorted_heights_left = sorted(sorted_heights, key = lambda x: (x[0], -x[1]), reverse=True)

        # Print everything:
        print(sorted_heights)
        print(sorted_heights_left)
        print(f'n = ${n}\nSOLUTION:')

        # Start at the highest point and look to the right:
        prev_y = sorted_heights[0][0]
        prev_x = sorted_heights[0][1]
        volume_filled = 0
        for i in range(1, n):
            y = sorted_heights[i][0]
            x = sorted_heights[i][1]
            if filled[x] == True:  # Skip if block already filled.
                continue
            if x - prev_x >= 2:  # Move to the right.
                print(f'RIGHT SPAN ${prev_x}[${prev_y}] > ${x}[${y}]')
                filled[x] = True
                for idx in range(prev_x + 1, x):
                    plus = max(y - height[idx], 0)
                    volume_filled += plus
                    filled[idx] = True
                    print(f' - plus (${plus}) ${idx} [${height[idx]}]   .... vol=${volume_filled}')
                prev_y = y
                prev_x = x
        
        # Start again at highest points and look left:
        prev_y = sorted_heights[0][0]
        prev_x = sorted_heights[0][1]  # Same starting point.
        for i in range(0, n):
            y = sorted_heights_left[i][0]
            x = sorted_heights_left[i][1]
            if filled[x] == True:  # Skip if block already filled.
                continue
            if prev_x - x >= 2:  # Move to the left.
                print(f'LEFT SPAN ${prev_x}[${prev_y}] > ${x}[${y}]')
                filled[x] = True
                for idx in range(prev_x - 1, x, -1):
                    plus = max(y - height[idx], 0)
                    volume_filled += plus
                    print(f' - plus (${plus}) ${idx} [${height[idx]}]   .... vol=${volume_filled}')
                    filled[idx] = True
                prev_y = y
                prev_x = x

        return volume_filled
Optimal Two Pointer Approach
# The faster two-pointer approach...
# This approach will take advantage of the fact that the water trapped
# at any position depends on the minimum of the highest bars on the left
# and right of that position.
#
#          |              _
#          |      _      | |_   _
#          |  _  | |# # #| | |#| |_
#          | | |#| | |#| | | | | | |
#          +-----------------------+
# height = [0,1,0,2,1,0,1,3,2,1,2,1] -> 6

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0

        n = len(height)
        left, right = 0, n - 1
        left_max, right_max = height[left], height[right]
        water = 0
        while left < right:
            if height[left] < height[right]:
                left += 1
                left_max = max(left_max, height[left])
                water += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                water += right_max - height[right]
        return water



(13) Roman to Integer (Easy) Solved

(view problem)

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

  • Symbol Values: I=1, V=5, X=10, L=50, C=100, D=500, M=1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.


Example:

  • Input:
    s = "MCMXCIV"
  • Output:
    1994


Solution
class Solution:
    def romanToInt(self, s: str) -> int:
        roman_char_to_int = {
            'I': 1,
            'V': 5,
            'X': 10,
            'L': 50,
            'C': 100,
            'D': 500,
            'M': 1000
        }
        #.  1.   2.    3.     4.    5.   6.    7.     8.      9.    10.
        #. 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IIX', 'X'
        #. 
        #. 'XXVII' -> 1+1+5+10+10  = 27
        #. 'XDM'   -> 1000-500-100 = 400 
        running_total = 0
        ahead_val = 0       # Value of the char in front of the current.
        for i in range(len(s) - 1, -1, -1):  # Backwards order.
            curr_char = s[i]
            curr_val = roman_char_to_int[curr_char]
            if ahead_val >= 0 and ahead_val > curr_val:
                running_total -= curr_val
            else:
                running_total += curr_val
                ahead_val = curr_val
        return running_total
Forward Search Variation
def romanToInt(s):
    roman_to_int = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    total = 0
    prev_value = 0
    for c in s:  # Search forwards.
        current_value = roman_to_int[c]
        if current_value > prev_value:
            total += current_value - 2 * prev_value  # Subtract previous value twice because it was added before.
        else:
            total += current_value
        prev_value = current_value
    return total



(12) Integer to Roman (Medium) Solved

(view problem)

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

  • Symbol Value
  • I 1
  • V 5
  • X 10
  • L 50
  • C 100
  • D 500
  • M 1000

For example, 2 is written as II in Roman numeral, just two one's added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

  • I can be placed before V (5) and X (10) to make 4 and 9.
  • X can be placed before L (50) and C (100) to make 40 and 90.
  • C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.


Example:

  • Input:
    num = 1994
  • Output:
    "MCMXCIV"


Solution
class Solution:
    def intToRoman(self, num: int) -> str:
        values = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        symbols = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]
        roman = ""
        for i in range(len(values)):
            while num >= values[i]:
                roman += symbols[i]
                num -= values[i]
        return roman
My Original Longwinded Approach
ROMAN_VALUES = [
            'I',  # 1.
            'V',  # 5.
            'X',  # 10.
            'L',  # 50.
            'C',  # 100.
            'D',  # 500.
            'M',  # 1000.
            '-', '-'
            ]

def get_roman_char(remainder: int, base_10: int) -> str:
  base_10_offset = base_10 * 2
  roman_1 = ROMAN_VALUES[base_10_offset]
  roman_5 = ROMAN_VALUES[base_10_offset + 1]
  roman_10 = ROMAN_VALUES[base_10_offset + 2]
  if remainder == 0:
    return ''
  if remainder == 1:
    return roman_1
  elif remainder == 2:
    return roman_1 + roman_1
  elif remainder == 3:
    return roman_1 + roman_1 + roman_1
  elif remainder == 4:
    return roman_1 + roman_5
  if remainder == 5:
    return roman_5
  elif remainder == 6:
    return roman_5 + roman_1
  elif remainder == 7:
    return roman_5 + roman_1 + roman_1
  elif remainder == 8:
    return roman_5 + roman_1 + roman_1 + roman_1
  elif remainder == 9:
    return roman_1 + roman_10
        
class Solution:
    def intToRoman(self, num: int) -> str:
        roman = ''
        base_10 = 0
        while num > 0:
            remainder = num % 10
            roman = get_roman_char(remainder, base_10) + roman
            num = int((num - remainder) / 10)
            base_10 += 1
        return roman



(58) Length of Last Word (Easy) Solved

(view problem)

Given a string s consisting of words and spaces, return the length of the last word in the string. A word is a maximal substring consisting of non-space characters only.


Example:

  • Input:
    "luffy is still joyboy"
  • Output:
    6


Solution
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        last_non_digit_idx = -1
        i = len(s) - 1
        while i >= 0:
            if s[i] == ' ':
                if last_non_digit_idx > -1:
                    return last_non_digit_idx - i
            elif last_non_digit_idx == -1:
                last_non_digit_idx = i
            i -= 1
        return last_non_digit_idx + 1  # If -1 returns 0.
Optimal Solution Using String Functions
It might defeat the purpose of the exercise, but turns out this is run faster using some build-in string functions in a single line of code...
class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        return len(s.rstrip().split(' ')[-1])



(14) Longest Common Prefix (Easy) Solved

(view problem)

Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string ("").


Example:

  • Input:
    strs = ["flower","flow","flight"]
  • Output:
    "fl"


Solution
class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ''
        i = 0
        while True:
            letter = ''
            for word in strs:
                if i >= len(word):
                    return word
                if letter == '':
                    letter = word[i]
                elif word[i] != letter:
                    return word[:i]
            i += 1
        return ''




(151) Reverse Words in a String (Medium) Solved

(view problem)

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.


Example:

  • Input:
    s = "a good example"
  • Output:
    "example good a"


Solution
class Solution:
    def reverseWords(self, s: str) -> str:
        new_words = []
        end_word = -1  # Index for the end of a word... -1 means not found.
        for i in range(len(s) - 1, -1, -1):    # Search backwards.
            letter = s[i]
            if end_word == -1:         # If end of word not found:
                if letter != ' ':      #  Non-space means:
                    end_word = i       #   End of word found.
            else:                      # Else:
                if letter == ' ':      #  Space means: add new word
                    new_words.append(s[i+1:end_word+1])
                    end_word = -1
        if end_word >= 0:
            new_words.append(s[0:end_word+1])
        return ' '.join(new_words)

        # LESS CODE, MORE SPACE:
        # words = s.split(' ')
        # final_words = []
        # for i in range(len(words) - 1, -1, -1):
        #     word = words[i]
        #     if word != '':
        #         final_words.append(word)
        # return ' '.join(final_words)




(6) Zigzag Conversion (Medium) Completed

(view problem)

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows: string convert(string s, int numRows);


Example:

  • Input:
    s = "PAYPALISHIRING", numRows = 3
  • Output:
    "PAHNAPLSIIGYIR"


Solution
# When we visualize the zigzag pattern
#
#   01234567890123
#   *     *     *     --> PINalsigYAHRPI
#    *   * *   * *
#     * *   * *
#      *     *
#   PaYPAlIsHIRiNg
#
# We realize that each "zig" or "zag" has a length of numRows + (numRows - 2).
# With this we can place characters in their appropriate position.

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1 or len(s) <= numRows:
            return s
        # Initialize rows:
        rows = [''] * numRows
        curRow = 0
        direction = -1
        for char in s:
            rows[curRow] += char
            # Change direction if at the top or bottom:
            if curRow == 0 or curRow == numRows - 1:
                direction *= -1
            curRow += direction
        return ''.join(rows)




(28) Find the Index of the First Occurrence in a String (Easy) Completed

(view problem)

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.


Example:

  • Input:
    haystack = "sadbutsad", needle = "sad"
  • Output:
    0


Solution
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        # Easy/cheat solution:
        # return haystack.find(needle)
        # Loop solution:
        for i in range(len(haystack) - len(needle) + 1):
            for j in range(len(needle)):
                if haystack[i + j] != needle[j]:
                    break
                if j >= len(needle) - 1:
                    return i
        return -1




(68) Text Justification (Hard) Solved

(view problem)

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified, and no extra space is inserted between words.

Note: A word is defined as a character sequence consisting of non-space characters only. Each word's length is guaranteed to be greater than 0 and not exceed maxWidth. The input array words contain at least one word.


Example:

  • Input:
    words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
  • Output:
    [ "This is an", "example of text", "justification. "]


Solution
class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        result = []          # Result to return (array of lines).
        current = []         # Words for the next line.
        num_of_letters = 0   # Total letters in line so far.

        for word in words:
            if num_of_letters + len(word) + len(current) > maxWidth:
                for i in range(maxWidth - num_of_letters):
                    current[i % (len(current) - 1 or 1)] += ' '
                result.append(''.join(current))
                current = []
                num_of_letters = 0
            current += [word]
            num_of_letters += len(word)

        result.append(' '.join(current).ljust(maxWidth, ' '))
        return result



Two Pointers


(125) Valid Palindrome (Easy) Solved

(view problem)

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.


Example:

  • Input:
    s = "A man, a plan, a canal: Panama"
  • Output:
    true


Solution
def is_letter(x: str) -> bool:
    # It is faster to use python's built-in "isalnum()",
    # but I just wanted to show how to do it in code.
    return (
        ('a' <= x <= 'z') or  # I've used chained comparisons (x < y < z).
        ('A' <= x <= 'Z') or
        ('0' <= x <= '9'))

class Solution:
    def isPalindrome(self, s: str) -> bool:
        i = 0
        j = len(s) - 1
        while i < j:
            if not is_letter(s[i]):
                i += 1
                continue
            if not is_letter(s[j]):
                j -= 1
                continue
            # Both are letters:
            elif s[i].upper() == s[j].upper():
                i += 1
                j -= 1
            else:
                return False
        return True




(392) Is Subsequence (Easy) Solved

(view problem)

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).


Example:

  • Input:
    s = "abc", t = "ahbgdc"
  • Output:
    true


Solution
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        if len(s) == 0:
            return True
        i = 0
        j = 0
        while i < len(t):
            if t[i] == s[j]:
                j += 1
                if j >= len(s):
                    return True
            i += 1
        return False




(167) Two Sum II - Input Array Is Sorted (Medium) Solved

(view problem)

Given a 1-indexed array of integer numbers that are already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1, and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.


Example:

  • Input:
    numbers = [2,7,11,15], target = 9
  • Output:
    [1,2]


Solution
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0
        right = len(numbers) - 1
        while left < right:
            current_sum = numbers[left] + numbers[right]
            if current_sum == target:
                return [left + 1, right + 1]  # One indexed.
            elif current_sum < target:
                left += 1
            else:
                right -= 1
        return []




(11) Container With Most Water (Medium) Solved

(view problem)

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.


Example:

  • Input:
    height = [1,8,6,2,5,4,8,3,7]
  • Output:
    49


Solution
class Solution:
    def maxArea(self, height: List[int]) -> int:
        if not height:
            return 0
        l, r = 0, len(height) - 1
        max_area = 0
        while l < r:
            area = (r - l) * min(height[l], height[r])
            max_area = max(max_area, area)
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return max_area




(15) 3Sum (Medium) Solved

(view problem)

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.


Example:

  • Input:
    nums = [-1,0,1,2,-1,-4]
  • Output:
    [[-1,-1,2],[-1,0,1]]


Solution
class Solution(object):
    def threeSum(self, nums):
        if not nums:
            return []

        nums.sort()
        results = []
        for i in range(0, len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:  # Skip duplicates for i.
                continue

            # Two pointer search inwards to find any pairs that sum with i to give 0.
            l, r = i + 1, len(nums) - 1
            while l < r:
                total = nums[i] + nums[l] + nums[r]
                # If the sum is zero, add the triplet.
                if total == 0:
                    results.append([nums[i], nums[l], nums[r]])
                    while l < r and nums[l] == nums[l+1]:     # Skip duplicates for l.
                        l += 1
                    while l < r and nums[r] == nums[r-1]:     # Skip duplicates for r.
                        r -= 1
                    l += 1
                    r -= 1
                elif total < 0:
                    l += 1
                else:
                    r -= 1
        return results



Sliding Window


(209) Minimum Size Subarray Sum (Medium) Solved

(view problem)

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to the target. If there is no such subarray, return 0 instead.


Example:

  • Input:
    target = 7, nums = [2,3,1,2,4,3]
  • Output:
    2


Solution
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        if not nums:
            return 0
        i, j = 0, 0  # Sliding window
        total = 0
        min_length = float('inf')
        while j < len(nums):
            total += nums[j]
            while total >= target:
                min_length = min(min_length, j - i + 1)
                total -= nums[i]
                i += 1
            j += 1
        return min_length if min_length < float('inf') else 0




(3) Longest Substring Without Repeating Characters (Medium) Solved

(view problem)

Given a string s, find the length of the longest substring without repeating characters.


Example:

  • Input:
    s = "abcabcbb"
  • Output:
    3


Solution
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0

        unique_chars = set()
        i, j = 0, 0  # Sliding window (start and end idx).
        max_unique_len = 0
        while j < len(s):
            char = s[j]
            if char in unique_chars:
                unique_chars.remove(s[i])
                i += 1
            else:
                max_unique_len = max(max_unique_len, j - i + 1)
                unique_chars.add(char)
                j += 1
        return max_unique_len




(30) Substring with Concatenation of All Words (Hard) NOT SOLVED ❌

(view problem)

You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated substring in s' is a substring that contains all the strings of any permutation of words concatenated.

For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated substring because it is not the concatenation of any permutation of words. Return the starting indices of all the concatenated substrings in s. You can return the answer in any order.


Example:

  • Input:
    s = "barfoothefoobarman", words = ["foo","bar"]
  • Output:
    [0,9]


Solution




(76) Minimum Window Substring (Hard) NOT SOLVED ❌

(view problem)

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.


Example:

  • Input:
    s = "ADOBECODEBANC", t = "ABC"
  • Output:
    "BANC"


Solution



Matrix


(36) Valid Sudoku (Medium) Solved

(view problem)

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable. Only the filled cells need to be validated according to the mentioned rules.


Example:

  • Input:
    board = \

[["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]

  • Output:
    true


Solution
SIDE = 9
BOX_SIDE = 3
BOXES_PER_SIDE = 3

def cell(board: List[List[str]], x:int, y:int):
    return board[y][x]

def value_already_appears(val: str, occurrences: list[int]) -> bool:
    if val == '.':
        return False
    idx: int = ord(val) - ord('1')
    if occurrences[idx] >= 1:
        return True
    else:
        occurrences[idx] = 1
        return False

def reset_occurrences(occurrences: list[int]) -> None:
    for i in range (len(occurrences)):
        occurrences[i] = 0

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        occurrences: list[int] = [0] * SIDE

        # For each column:
        for x in range(SIDE):
            reset_occurrences(occurrences)
            for y in range(SIDE):
                if value_already_appears(cell(board, x, y), occurrences):
                    return False

        # For each row:
        for y in range(SIDE):
            reset_occurrences(occurrences)
            for x in range(SIDE):
                if value_already_appears(cell(board, x, y), occurrences):
                  return False
        
        # For each box:
        for x_box in range(BOXES_PER_SIDE):
            for y_box in range(BOXES_PER_SIDE):
                reset_occurrences(occurrences)
                for x_offset in range(BOX_SIDE):
                    for y_offset in range(BOX_SIDE):
                        x = x_box * BOX_SIDE + x_offset
                        y = y_box * BOX_SIDE + y_offset
                        if value_already_appears(cell(board, x, y), occurrences):
                            return False

        return True




(54) Spiral Matrix (Medium) Solved

(view problem)

Given an m x n matrix, return all elements of the matrix in spiral order.


Example:

  • Input:
    matrix = [[1,2,3],[4,5,6],[7,8,9]]
  • Output:
    [1,2,3,6,9,8,7,4,5]


Solution
NUM_DIRECTIONS = 4

def is_inside(x:int, y:int, x_min:int,
              y_min:int, x_max:int, y_max:int) -> bool:
    return (x_min < x < x_max) and (y_min < y < y_max)
    
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        """Return items in a clockwise spiral, starting at 0,0."""
        if not matrix or len(matrix) == 0:
            return []

        HEIGHT = len(matrix)
        WIDTH = len(matrix[0])

        x_min = -1
        y_min = -1
        x_max = WIDTH
        y_max = HEIGHT
        curr_direction = 0

        spiral = []
        idx = [0, 0]  # Current position.
        new_cell = True
        while True:
            # Append cells to spiral (if new):
            x = idx[0]  # Looking for new position.
            y = idx[1]  # Looking for new position.
            if new_cell:
                spiral.append(matrix[y][x])
                new_cell = False

            # Progress forwards:
            if curr_direction == 0:  # Left.
                x += 1
            if curr_direction == 1:  # Down.
                y += 1
            if curr_direction == 2:  # Right.
                x -= 1
            if curr_direction == 3:  # Up.
                y -= 1

            # Check if new cell is inside:
            inside = is_inside(x, y, x_min, y_min, x_max, y_max)

            # Advance to this new cell, else change directions:
            if inside:
                idx = [x, y]
                new_cell = True
            else:
                if curr_direction == 0:  # Left.    -> y_min += 1
                    y_min += 1
                if curr_direction == 1:  # Down.    -> x_max -= 1
                    x_max -= 1
                if curr_direction == 2:  # Right.  -> y_max -= 1
                    y_max -= 1
                if curr_direction == 3:  # Up.     -> x_min += 1
                    x_min += 1
                curr_direction = (curr_direction + 1) % NUM_DIRECTIONS
                if y_min >= y_max -1 and x_min >= x_max - 1:
                    break
        return spiral
More Concise, Full Sides
A variation where we go all the way along each direction with a separate loop.
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        """Return items in a clockwise spiral, starting at 0,0."""
        if not matrix or len(matrix) == 0:
            return []

        m, n = len(matrix), len(matrix[0])
        top, bottom, left, right = 0, m-1, 0, n-1
        result = []

        while left <= right and top <= bottom:
            # Traverse left to right:
            for j in range(left, right+1):
                result.append(matrix[top][j])
            top += 1
            # Traverse top to bottom:
            for i in range(top, bottom+1):
                result.append(matrix[i][right])
            right -= 1
            # Traverse right to left (ensure top is not greater than bottom):
            if top <= bottom:
                for j in range(right, left-1, -1):
                    result.append(matrix[bottom][j])
                bottom -= 1
            # Traverse bottom to top (ensure left is not greater than right):
            if left <= right:
                for i in range(bottom, top-1, -1):
                    result.append(matrix[i][left])
                left += 1
        return result



(48) Rotate Image (Medium) Solved

(view problem)

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.


Example:

  • Input:
    matrix = [[1,2,3],[4,5,6],[7,8,9]]
  • Output:
    [[7,4,1],[8,5,2],[9,6,3]]


Solution
class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        if not matrix or len(matrix) == 0:
            return

        HEIGHT = len(matrix)
        WIDTH = len(matrix[0])
        # Part that repeats (bit to rotate):
        HALF_WIDTH = int((WIDTH + 1) / 2)
        HALF_HEIGHT = int((HEIGHT) / 2)

        for y in range (HALF_HEIGHT):
            for x in range (HALF_WIDTH):
                x_max = WIDTH - x - 1
                y_max = HEIGHT - y - 1
                matrix[y][x], matrix[x][y_max], matrix[y_max][x_max], matrix[x_max][y] = (
                    matrix[x_max][y], matrix[y][x], matrix[x][y_max], matrix[y_max][x_max]
                )




(73) Set Matrix Zeroes (Medium) Solved

(view problem)

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

You must do it in place.


Example:

  • Input:
    matrix = [[1,1,1],[1,0,1],[1,1,1]]
  • Output:
    [[1,0,1],[0,0,0],[1,0,1]]


Solution
class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        if not matrix:
            return
        HEIGHT = len(matrix)
        WIDTH = len(matrix[0])
        cols_to_zero = set()
        rows_to_zero = set()
        # If row is zeroed out > we can break.
        for y in range(HEIGHT):
            for x in range(WIDTH):
                if matrix[y][x] == 0:
                    cols_to_zero.add(x)
                    rows_to_zero.add(y)

        for x in cols_to_zero:
            for y in range(HEIGHT):
                matrix[y][x] = 0 
        for y in rows_to_zero:
            for x in range(WIDTH):
                matrix[y][x] = 0




(289) Game of Life (Medium) Solved

(view problem)

According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.


Example:

  • Input:
    board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
  • Output:
    [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]


Solution
def num_living_neighbors(board: list[list[int]], x: int, y: int, w: int, h: int) -> int:
    living = 0
    for y_offset in range(max(0, y-1), min(y+1, h - 1)+1):
        for x_offset in range(max(0, x-1), min(x+1, w - 1)+1):
            # print('  ', x_offset, y_offset)
            if board[y_offset][x_offset] % 2 == 1:
                if (y_offset != y or x_offset != x):
                    living += 1
    return living 

class Solution:
    def gameOfLife(self, board: List[List[int]]) -> None:
        if not board or len(board) == 0:
            return
        HEIGHT = len(board)
        WIDTH = len(board[0])

        # Determine changes:
        #   KEY:
        #   0 = was dead > stay dead.
        #   1 = was live > stay live.
        #   2 = was dead > now LIVE.
        #   3 = was live > now DEAD.
        for y in range (HEIGHT):
            for x in range (WIDTH):
                live = board[y][x]
                living_neighbors = num_living_neighbors(board, x, y, WIDTH, HEIGHT)
                if live:
                    if living_neighbors < 2:  # Under-population.
                        board[y][x] = 3  # Dies.
                    elif living_neighbors > 3:  # Over-population.
                        board[y][x] = 3   # Dies.
                    # else:
                    #     board[y][x] = 1   # Stay alive.
                else:
                    if living_neighbors == 3:  # Repoduction.
                        board[y][x] = 2  # Ressurected.

        # Apply changes:
        for y in range (HEIGHT):
            for x in range (WIDTH):
                if board[y][x] >= 2:
                    board[y][x] = (board[y][x] + 1) % 2



Hashmap


(383) Ransom Note (Easy) Solved

(view problem)

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in the magazine can only be used once in ransomNote.


Example:

  • Input:
    ransomNote = "aa", magazine = "aab"
  • Output:
    true


Solution
def create_letter_freq_dict(text: str) -> dict[str,int]:
    freq = {}
    for letter in text:
        if letter not in freq:
            freq[letter] = 0
        freq[letter] += 1
    return freq

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        randsome_freq = create_letter_freq_dict(ransomNote)
        magazine_freq = create_letter_freq_dict(magazine)
        # TODO(noske): Actually we could just iterate magazine and
        # subtract from `randsome_freq` with each new letter needed.
        for letter, freq in randsome_freq.items():
            if letter not in magazine_freq:
                return False
            if magazine_freq[letter] < freq:
                return False
        return True
Only One Hashmap (better)
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # Create a dictionary to store occurrence counts of characters in magazine
        mag_char_count = {}
        for char in magazine:
            mag_char_count[char] = mag_char_count.get(char, 0) + 1

        # Check if ransom note can be constructed from the magazine
        for char in ransomNote:
            # If char not in magazine or its count has exhausted, return False
            if char not in mag_char_count or mag_char_count[char] == 0:
                return False
            mag_char_count[char] -= 1
        return True



(205) Isomorphic Strings (Easy) Solved

(view problem)

Given two strings s and t, determine if they are isomorphic.

Two strings s and t are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.


Example:

  • Input:
    s = "egg", t = "add"
  • Output:
    true


Solution
class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_to_t_mapping = {}
        t_to_s_mapping = {}
        for s_letter, t_letter in zip(s, t):  # NOTE: zip is a special operator.
            if s_letter in s_to_t_mapping:
                if s_to_t_mapping[s_letter] != t_letter:
                    return False
            else:
                s_to_t_mapping[s_letter] = t_letter
            if t_letter in t_to_s_mapping:
                if t_to_s_mapping[t_letter] != s_letter:
                    return False
            else:
                t_to_s_mapping[t_letter] = s_letter
        return True




(290) Word Pattern (Easy) Solved

(view problem)

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.


Example:

  • Input:
    pattern = "aaaa", s = "dog cat cat dog"
  • Output:
    false


Solution
# pattern = "abba", s = "dog cat cat dog" -> True
#
# PSUEDO:
#  Break apart s:   [dog, cat, cat, dog]
#  Iterate both arrays and 
#    create dict for pattern to s:  { a:'dog', b:'cat' }
#      > if contradicts, then return false.
#
#  Create dict for both arrays {'dog': 0, 'cat': 1}
#  resolve to array:           [0,1,1,0]
#  Check both arrays are equal.

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        words = s.split()
        if len(words) != len(pattern):
            return False

        letter_map = {}
        word_map = {}
        for i in range(len(words)):
            word = words[i]
            letter = pattern[i]
            if letter in letter_map:
                if letter_map[letter] != word:
                    return False
            else:
                letter_map[letter] = word
            if word in word_map:
                if word_map[word] != letter:
                    return False
            else:
                word_map[word] = letter
        return True




(242) Valid Anagram (Easy) Solution

(view problem)

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.


Example:

  • Input:
    s = "anagram", t = "nagaram"
  • Output:
    true


Solution
def get_char_frequency(s: str) -> dict:
    """Return a dictionary representing the frequency of characters in the string."""
    char_count = {}    
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    return char_count

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False
        return get_char_frequency(s) == get_char_frequency(t)
Solution Using Counter collections
from collections import Counter

class Solution:
    def isAnagram(s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

# Testing the function with given examples:
print(isAnagram("anagram", "nagaram"))  # Output: True
print(isAnagram("rat", "car"))          # Output: False



(49) Group Anagrams (Medium) Solved

(view problem)

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.


Example:

  • Input:
    strs = ["eat","tea","tan","ate","nat","bat"]
  • Output:
    [["bat"],["nat","tan"],["ate","eat","tea"]]


Solution
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        sorted_strs = {}
        for i, word in enumerate(strs):
            chars = []
            for l in word:
                chars.append(l)
            chars.sort()
            sorted_str = ''.join(chars)
            if not sorted_str in sorted_strs:
                sorted_strs[sorted_str] = []
            sorted_strs[sorted_str].append(word)
        # print(sorted_strs)
        result = []
        for _, words_arr in sorted_strs.items():
            result.append(words_arr)
        return result




(49) Two Sum (Easy) Solved

(view problem)

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.


Example:

  • Input:
    strs = ["eat","tea","tan","ate","nat","bat"]
  • Output:
    [["bat"],["nat","tan"],["ate","eat","tea"]]


Solution
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        sorted_strs = {}
        for i, word in enumerate(strs):
            chars = []
            for l in word:
                chars.append(l)
            chars.sort()
            sorted_str = ''.join(chars)
            if not sorted_str in sorted_strs:
                sorted_strs[sorted_str] = []
            sorted_strs[sorted_str].append(word)
        # print(sorted_strs)
        result = []
        for _, words_arr in sorted_strs.items():
            result.append(words_arr)
        return result




(202) Happy Number (Easy) Solved

(view problem)

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits. Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1. Those numbers for which this process ends in 1 are happy. Return true if n is a happy number, and false if not.


Example:

  • Input:
    n = 19
  • Output:
    true # Explanation: 1^2 + 9^2 = 82, 8^2 + 2^2 = 68, 6^2 + 8^2 = 100, 1^2 + 0^2 + 0^2 = 1


Solution
MAX_ITERATIONS = 100

def num_to_digit_array(n: int) -> list[int]:
    arr = []
    while n > 0:
        last_digit = n % 10
        n = int(n / 10)
        arr.append(last_digit)
    arr.reverse()
    return arr

def sum_of_squares(arr: list[int]) -> int:
    total = 0
    for x in arr:
        total += x * x
    return total

class Solution:
    def isHappy(self, n: int) -> bool:
        first_square = 0
        for i in range(MAX_ITERATIONS):
            arr = num_to_digit_array(n)
            n = sum_of_squares(arr)
            
            if n == 1:  # Exit if 1 (happy number found).
                return True
            if first_square == 0:    # Set first square just once.
                first_square = n
            elif n == first_square:  # Exit if looped back to first square.
                return False
        return False
Floyd's Cycle-Finding Algorithm
We could also use the Floyd's cycle-finding algorithm (also known as the "tortoise and the hare" algorithm) to detect if there's a cycle. The idea is to transform the number repeatedly using the rule given, and do this transformation at two speeds - one "fast" and one "slow". If there's a cycle (i.e., the number isn't happy), the two speeds will eventually produce the same number. While checking the sum of squares of digits, if we ever encounter the number 1, it's a happy number. Here's how you can implement it:
def get_next(n):
    """Get the next number according to the rule."""
    total_sum = 0
    while n > 0:
        n, digit = divmod(n, 10)
        total_sum += digit ** 2
    return total_sum

class Solution(object):
    def isHappy(self, n):
        # Using Floyd's Cycle-Finding Algorithm
        slow, fast = n, get_next(n)
        while fast != 1 and slow != fast:
            slow = get_next(slow)
            fast = get_next(get_next(fast))
        return fast == 1

# Testing the function with given examples:
# print(isHappy(19))  # Output: True
# print(isHappy(2))   # Output: False



(219) Contains Duplicate II (Easy) Solved

(view problem)

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.


Example:

  • Input:
    nums = [1,2,3,1], k = 3
  • Output:
    true


Solution
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        num_to_max_idx = {}  # A map of number values to the max index.
        for i, num in enumerate(nums):
            if num in num_to_max_idx:
                if abs(i - num_to_max_idx[num]) <= k:
                    return True
            num_to_max_idx[num] = i
        return False




(128) Longest Consecutive Sequence (Medium) NOT SOLVED ❌

(view problem)

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.


Example:

  • Input:
    nums = [100,4,200,1,3,2]
  • Output:
    4 # Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.


Solution



Intervals


(228) Summary Ranges (Easy) Solved

(view problem)

You are given a sorted unique integer array nums.

A range [a,b] is the set of all integers from a to b (inclusive).

Return the smallest sorted list of ranges that cover all the numbers in the array exactly. That is, each element of nums is covered by exactly one of the ranges, and there is no integer x such that x is in one of the ranges but not in nums.

Each range [a,b] in the list should be output as:

  • "a->b" if a != b
  • "a" if a == b


Example:

  • Input:
    nums = [0,1,2,4,5,7]
  • Output:
    ["0->2","4->5","7"] # The ranges are: [0,2] --> "0->2"


Solution
def range_to_string(start: int, end: int) -> str:
    if start == end:
        return str(start)
    else:
        return str(start) + '->' + str(end)

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        if not nums or len(nums) == 0:
            return []
        arr = []
        start_idx = 0
        i = 0
        while True:
            i += 1
            if i >= len(nums):
                arr.append(range_to_string(nums[start_idx], nums[i - 1]))
                break
            if nums[i] != nums[i-1] + 1:
                arr.append(range_to_string(nums[start_idx], nums[i - 1]))
                start_idx = i
        return arr




(56) Merge Intervals (Medium) Solved

(view problem)

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.


Example:

  • Input:
    intervals = [[1,3],[2,6],[8,10],[15,18]]
  • Output:
    [[1,6],[8,10],[15,18]] # Since intervals [1,3] and [2,6] overlap, merge them into [1,6]


Solution
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if not intervals:
            return []
        if len(intervals) == 1:
            return intervals
        print('intervals=', intervals)
        intervals = sorted(intervals, key=lambda interval: interval[0])
        print('AFTER SORTING=', intervals)

        results = [intervals[0]] # Stack.
        for i in range(1, len(intervals)):
            if results[-1][1] >= intervals[i][0]:
                if results[-1][1] < intervals[i][1]:
                  results[-1][1] = intervals[i][1]
            else:
                results.append(intervals[i])
        return(results)




(57) Insert Interval (Medium) Solved

(view problem)

You are given an array of non-overlapping intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.


Example:

  • Input:
    intervals = [[1,3],[6,9]], newInterval = [2,5]
  • Output:
    [[1,5],[6,9]]


Solution
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        result = []
        for interval in intervals:
            # If current interval is completely before newInterval:
            if interval[1] < newInterval[0]:
                result.append(interval)
            # If current interval is completely after newInterval:
            elif interval[0] > newInterval[1]:
                result.append(newInterval)
                newInterval = interval  # Replace to mean next interval.
            # If there's an overlap:
            else:
                newInterval[0] = min(newInterval[0], interval[0])
                newInterval[1] = max(newInterval[1], interval[1])
        result.append(newInterval)
        return result




(452) Minimum Number of Arrows to Burst Balloons (Medium) Solved

(view problem)

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.


Example:

  • Input:
    points = [[10,16],[2,8],[1,6],[7,12]]
  • Output:
    2


Solution



Stack


(20) Valid Parentheses (Easy) Solved

(view problem)

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order. Every close bracket has a corresponding open bracket of the same type.


Example:

  • Input:
    s = "()[]{}"
  • Output:
    true # But would be false for anything like: "(]".


Solution
class Solution:
    def isValid(self, s: str) -> bool:
        # '()[]{}' -> true
        bracket_matches = {
            ')': '(',
            ']': '[', 
            '}': '{', 
            }   # Note: Try chr(ord(bracket) - 1) > does not work for all these.
        brackets_stack = []
        for bracket in s:
            if bracket in bracket_matches:
                bracket_match = bracket_matches[bracket]
                if not brackets_stack or brackets_stack.pop() != bracket_match:
                    return False
            else:
                brackets_stack.append(bracket)
        return len(brackets_stack) == 0




(71) Simplify Path (Medium) Solved

(view problem)

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

  • The path starts with a single slash '/'.
  • Any two directories are separated by a single slash '/'.
  • The path does not end with a trailing '/'.
  • The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')
  • Return the simplified canonical path.


Example:

  • Input:
    path = "/home//foo/"
  • Output:
    "/home/foo" # In the canonical path, multiple consecutive slashes are replaced by a single one.


Solution
class Solution:
    def simplifyPath(self, path: str) -> str:
        folders = path.split('/')
        final_folders = []
        for folder in folders:
            if folder == '..':
                if len(final_folders) > 0:
                    final_folders.pop()
            elif folder == '.' or folder == '':
                continue
            else:
                final_folders.append(folder)
        return '/' + '/'.join(final_folders)




(155) Min Stack (Medium) ) SolvedSolved*

(view problem)

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

  • MinStack() initializes the stack object.
  • void push(int val) pushes the element val onto the stack.
  • void pop() removes the element on the top of the stack.
  • int top() gets the top element of the stack.
  • int getMin() retrieves the minimum element in the stack.

You must implement a solution with O(1) time complexity for each function.


Example:

  • Input:
    ["MinStack","push","push","push","getMin","pop","top","getMin"] ... [[],[-2],[0],[-3],[],[],[],[]]
  • Output:
    [null,null,null,null,-3,null,0,-2]


Solution
class MinStack:
    def __init__(self):
        self.mainStack = []    # To store all the elements.
        self.minStack = []     # To keep track of the minimum at each state.

    def push(self, val: int) -> None:
        self.mainStack.append(val)
        # If the minStack is empty or the current value is less than or
        # equal to the top of minStack, push the current value onto minStack
        if not self.minStack or val <= self.minStack[-1]:
            self.minStack.append(val)       

    def pop(self) -> None:
        if not self.mainStack:
            return
        # If the top of mainStack is equal to the top of minStack,
        # pop from minStack as well.
        if self.mainStack[-1] == self.minStack[-1]:
            self.minStack.pop()
        self.mainStack.pop()

    def top(self) -> int:
        if not self.mainStack:
            return -1
        return self.mainStack[-1]

    def getMin(self) -> int:
        if not self.minStack:
            return -1
        return self.minStack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()




(150) Evaluate Reverse Polish Notation (Medium) NOT SOLVED ❌

(view problem)

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

  • The valid operators are '+', '-', '*', and '/'.
  • Each operand may be an integer or another expression.
  • The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.


Example:

  • Input:
    tokens = ["2","1","+","3","*"]
  • Output:
    9 # Explanation: ((2 + 1) * 3) = 9


Solution




(224) Basic Calculator (Hard) NOT SOLVED ❌

(view problem)

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function that evaluates strings as mathematical expressions, such as eval().


Example:

  • Input:
    s = "(1+(4+5+2)-3)+(6+8)"
  • Output:
    23


Solution



Linked List


(141) Linked List Cycle (Easy) Solved

(view problem)

Given head, the head of a linked list, determines if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that the tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.


Example:

  • Input:
    head = [3,2,0,-4], pos = 1
  • Output:
    true # Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).


Solution
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head == None:
            return False
        prev_nodes_set = set()
        n = head
        while n.next:
            prev_nodes_set.add(n)
            n = n.next
            if n in prev_nodes_set:
                return True
        return False




(2) Add Two Numbers (Medium) Solved

(view problem)

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.


Example:

  • Input:
    l1 = [2,4,3], l2 = [5,6,4]
  • Output:
    [7,0,8]. # Explanation: 342 + 465 = 807.


Solution
def get_value(n: Optional[ListNode]) -> int:
    if n == None:
        return None
    return n.val

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        new_list_head = None
        prev_node = None
        carry_over = 0
        while l1 or l2 or carry_over:
            next_digit = carry_over
            if l1:
                next_digit += l1.val
                l1 = l1.next
            if l2:
                next_digit += l2.val
                l2 = l2.next
            carry_over = next_digit // 10
            next_digit = next_digit % 10
            
            new_node = ListNode(next_digit)
            if not new_list_head:
                new_list_head = new_node
            else:
                prev_node.next = new_node
            prev_node = new_node
    
        return new_list_head




(21) Merge Two Sorted Lists (Easy) Solved

(view problem)

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.


Example:

  • Input:
    list1 = [1,2,4], list2 = [1,3,4]
  • Output:
    [1,1,2,3,4,4]


Solution
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode],
                            list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 and not list2:
            return None

        l1 = list1
        l2 = list2
        new_list_head = None
        new_node = None
        pre_node = None

        while l1 or l2:
            if not l1:
                new_node = ListNode(l2.val)
                l2 = l2.next
            elif not l2:
                new_node = ListNode(l1.val)
                l1 = l1.next
            elif l1.val < l2.val:
                new_node = ListNode(l1.val)
                l1 = l1.next
            else:
                new_node = ListNode(l2.val)
                l2 = l2.next

            if new_list_head == None:
                new_list_head = new_node
            else:
                prev_node.next = new_node
            prev_node = new_node
        return new_list_head




(138) Copy List with Random Pointer (Medium) NOT SOLVED ❌

(view problem)

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.


Example:

  • Input:
    head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
  • Output:
    [[7,null],[13,0],[11,4],[10,2],[1,0]]


Solution




(92) Reverse Linked List II (Medium) NOT SOLVED ❌

(view problem)

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.


Example:

  • Input:
    head = [1,2,3,4,5], left = 2, right = 4
  • Output:
    [1,4,3,2,5]


Solution




(25) Reverse Nodes in k-Group (Hard) NOT SOLVED ❌

(view problem)

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.


Example:

  • Input:
    head = [1,2,3,4,5], k = 2
  • Output:
    [2,1,4,3,5]


Solution




(19) Remove Nth Node From End of List (Medium) Solved

(view problem)

Given the head of a linked list, remove the nth node from the end of the list and return its head.


Example:

  • Input:
    head = [1,2,3,4,5], n = 2
  • Output:
    [1,2,3,5]


Solution
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head is None:
            return head
        # Create a dummy node that precedes the head.
        dummy = ListNode(-1)
        dummy.next = head

        first = dummy  # To move "n" spots ahead of "second".
        second = dummy
        for _ in range(n + 1):
            first = first.next
        while first:
            first = first.next
            second = second.next
        second.next = second.next.next
        return dummy.next




(82) Remove Duplicates from Sorted List II (Medium) Solved

(view problem)

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.


Example:

  • Input:
    head = [1,2,3,3,4,4,5]
  • Output:
    [1,2,5]


Solution
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(-999)  # Value that doesn't match first element.
        dummy.next = head
        prev = dummy
        current = head
        while current:
            # Check if current node is the start of a sequence of duplicates:
            if current.next and current.val == current.next.val:
                # Skip all the duplicates:
                while current.next and current.val == current.next.val:
                    current = current.next
                # After skipping all duplicates, link previous node to the next distinct node.
                prev.next = current.next
            else:
                prev = current
            current = current.next
        return dummy.next




(61) Rotate List (Medium) Solved

(view problem)

Given the head of a linked list, rotate the list to the right by k places.


Example:

  • Input:
    head = [1,2,3,4,5], k = 2
  • Output:
    [4,5,1,2,3]


Solution
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if head is None or k == 0:
            return head
        # Detemine length:
        end_node = head
        length = 1
        while end_node.next:
            end_node = end_node.next
            length += 1

        new_start_idx = length - (k % length)
        end_node.next = head  # Make it loop.

        # Locate new end node:
        new_end_node = head
        for _ in range(new_start_idx - 1):
            new_end_node = new_end_node.next
        new_head = new_end_node.next
        new_end_node.next = None

        return new_head




(86) Partition List (Medium) NOT SOLVED ❌

(view problem)

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.


Example:

  • Input:
    head = [1,4,3,2,5,2], x = 3
  • Output:
    [1,2,2,4,3,5]


Solution




(146) LRU Cache (Medium) Solved*

(view problem)

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

  • LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
  • int get(int key) Return the value of the key if the key exists, otherwise return -1.
  • void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.


Example:

  • Input:
    ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
  • Output:
    [null, null, null, 1, null, -1, null, -1, 3, 4]


Solution
class ListNode:
    # Double linked.
    def __init__(self, key=0, val=0, prev=None, next=None):
        self.key = key
        self.val = val
        self.prev = prev
        self.next = next
        
class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.d = {}
        self.head = None
        self.tail = None

    def _remove(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev

    def _add_to_tail(self, node):
        if self.tail:
            self.tail.next = node
            node.prev = self.tail
            node.next = None
            self.tail = node
        else:
            self.head = self.tail = node

    def get(self, key: int) -> int:
        if key not in self.d:
            return -1
        node = self.d[key]
        self._remove(node)
        self._add_to_tail(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.d:
            self._remove(self.d[key])
        node = ListNode(key, value)
        self._add_to_tail(node)
        self.d[key] = node
        
        if len(self.d) > self.capacity:
            to_remove = self.head
            self._remove(to_remove)
            del self.d[to_remove.key]

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)



Binary Tree General


(104) Maximum Depth of Binary Tree (Easy) Solved

(view problem)

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.


Example:

  • Input:
    root = [3,9,20,null,null,15,7]
  • Output:
    3


Solution
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def max_depth(n: TreeNode) -> int:
    """Return max depth."""
    if n == None:
        return 0
    left_depth = max_depth(n.left) + 1
    right_depth = max_depth(n.right) + 1
    return max(left_depth, right_depth)

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return max_depth(root)




(100) Same Tree (Easy) Solved

(view problem)

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.


Example:

  • Input:
    p = [1,2,3], q = [1,2,3]
  • Output:
    true


Solution
def is_same_tree(p: TreeNode, q: TreeNode) -> bool:
    if p == None and q == None:
        return True
    if p == None or q == None:
        return False
    if p.val != q.val:
        return False
    return (is_same_tree(p.left, q.left) and 
            is_same_tree(p.right, q.right))

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        return is_same_tree(p, q)




(226) Invert Binary Tree (Easy) Solved

(view problem)

Given the root of a binary tree, invert the tree, and return its root.


Example:

  • Input:
    root = [4,2,7,1,3,6,9]
  • Output:
    [4,7,2,9,6,3,1]


Solution
def invert_tree(n: Optional[TreeNode]):
    if not n:
        return
    n.left, n.right =  n.right, n.left
    invert_tree(n.left)
    invert_tree(n.right)

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        invert_tree(root)
        return root




(101) Symmetric Tree (Easy) Solved

(view problem)

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).


Example:

  • Input:
    root = [1,2,2,3,4,4,3]
  • Output:
    true


Solution
def are_symmetric(left: Optional[TreeNode], right: Optional[TreeNode]):
    has_left = left != None
    has_right = right != None
    if has_left != has_right:
        return False
    
    if not has_left and not has_right:
         return True
    return (
        left.val == right.val and 
        are_symmetric(left.left, right.right) and
        are_symmetric(left.right, right.left))

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        return are_symmetric(root.left, root.right)




(105) Construct Binary Tree from Preorder and Inorder Traversal (Medium) NOT SOLVED ❌

(view problem)

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.


Example:

  • Input:
    preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
  • Output:
    [3,9,20,null,null,15,7]


Solution




(106) Construct Binary Tree from Inorder and Postorder Traversal (Medium) NOT SOLVED ❌

(view problem)

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.


Example:

  • Input:
    inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
  • Output:
    [3,9,20,null,null,15,7]


Solution




(117) Populating Next Right Pointers in Each Node II (Medium) NOT SOLVED ❌

([UUUUUURRRRRRLLL view problem])

Given a binary tree

struct Node {

 int val;
 Node *left;
 Node *right;
 Node *next;

}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.


Example:

  • Input:
    root = [1,2,3,4,5,null,7]
  • Output:
    [1,#,2,3,#,4,5,7,#]

Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.


Solution




(114) Flatten Binary Tree to Linked List (Medium) NOT SOLVED ❌

(view problem)

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The "linked list" should be in the same order as a pre-order traversal of the binary tree.


Example:

  • Input:
    root = [1,2,5,3,4,null,6]
  • Output:
    [1,null,2,null,3,null,4,null,5,null,6]


Solution




(112) Path Sum (Easy) Solved

(view problem)

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.


Example:

  • Input:
    root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
  • Output:
    true


Solution
def has_path_sum(n: Optional[TreeNode], target_sum: int, curr_sum: int) -> bool:
    if n == None:
        return False
    curr_sum += n.val
    if not n.left and not n.right:
        return curr_sum == target_sum
    return (has_path_sum(n.left, target_sum, curr_sum) or 
            has_path_sum(n.right, target_sum, curr_sum))

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return has_path_sum(root, targetSum, 0)




(129) Sum Root to Leaf Numbers (Medium) Solved

(view problem)

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123. Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.


Example:

  • Input:
    root = [1,2,3]
  • Output:
    25


Solution
def sum_leaves(node: Optional[TreeNode], num: int) -> int:
    if not node:
        return 0

    num = (num * 10) + node.val
    if node.left == None and node.right == None:
        return num
    return (sum_leaves(node.left, num) +
            sum_leaves(node.right, num))
    
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        return sum_leaves(root, 0)




(124) Binary Tree Maximum Path Sum (Hard) Solved

(view problem)

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

The path sum of a path is the sum of the node's values in the path.

Given the root of a binary tree, return the maximum path sum of any non-empty path.


Example:

  • Input:
    root = [1,2,3]
  • Output:
    6


Solution




(173) Binary Search Tree Iterator (Medium) NOT SOLVED ❌

([UUUUUURRRRRRLLL view problem])

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer. Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.


Example:

  • Input:
    ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"] [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
  • Output:
    [null, 3, 7, true, 9, true, 15, true, 20, false]


Solution




(222) Count Complete Tree Nodes (Easy) Solved

(view problem)

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.


Example:

  • Input:
    [1,2,3,4,5,6]
  • Output:
    6


Solution
def leaf_exists(root: Optional[TreeNode], max_depth: int, last_level_idx: int) -> bool:
    n = root
    depth = 0
    while n:
        depth += 1
        mid = pow(2, max_depth - depth) / 2
        if last_level_idx < mid:
            n = n.left
        else:
            n = n.right
            last_level_idx -= mid
    return depth == max_depth

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if root == None:
            return 0

        # Navigate left side to determine tree depth:
        n = root
        max_depth = 0
        while n:
            max_depth += 1
            n = n.left
        max_nodes_for_given_depth = pow(2, max_depth) - 1

        # Do binary searches down to the last level to find
        # where last last node exists:
        low, high = 0, pow(2, max_depth - 1) - 1

        last_exists_idx = -1
        prev_mid = -1
        while low <= high:
            mid = (low + high) // 2
            exists = leaf_exists(root, max_depth, mid)
            if exists:
                low = mid + 1
            else:
                high = mid - 1
        return pow(2, max_depth - 1) + low - 1




(236) Lowest Common Ancestor of a Binary Tree (Medium) Solved

(view problem)

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”


Example:

  • Input:
    root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
  • Output:
    3


Solution





Binary Tree BFS


(199) Binary Tree Right Side View (Medium) NOT SOLVED ❌

(view problem)

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.


Example:

  • Input:
    root = [1,2,3,null,5,null,4]
  • Output:
    [1,3,4]


Solution




(637) Average of Levels in Binary Tree (Easy) NOT SOLVED ❌

(view problem)

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10^-5 of the actual answer will be accepted.


Example:

  • Input:
    root = [3,9,20,null,null,15,7]
  • Output:
    [3.00000,14.50000,11.00000]


Solution
from collections import deque

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        
        queue = deque()
        queue.append(root)
        results = []
        while queue:
            nodes_this_level = len(queue)
            sum_for_level = 0
            for i in range(nodes_this_level):
                n = queue.popleft()
                if not n:
                    continue
                sum_for_level += n.val
                if n.left:
                    queue.append(n.left)
                if n.right:
                    queue.append(n.right)
            results.append(sum_for_level / nodes_this_level)
        return results




(102) Binary Tree Level Order Traversal (Medium) NOT SOLVED ❌

(view problem)

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).


Example:

  • Input:
    root = [3,9,20,null,null,15,7]
  • Output:
    [[3],[9,20],[15,7]]


Solution




(102) Binary Tree Zigzag Level Order Traversal (Medium) NOT SOLVED ❌

(view problem)

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).


Example:

  • Input:
    root = [3,9,20,null,null,15,7]
  • Output:
    [[3],[20,9],[15,7]]


Solution



Binary Search Tree


(530) Minimum Absolute Difference in BST (Easy) Solved

(view problem)

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.


Example:

  • Input:
    root = [4,2,6,1,3]
  • Output:
    1


Solution
MAX_DIFF = float('inf')

def bst_to_sorted_arr(n: Optional[TreeNode], arr: list[int]) -> None:
    if n:
        bst_to_sorted_arr(n.left, arr)
        arr.append(n.val)
        bst_to_sorted_arr(n.right, arr)

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        arr = []
        bst_to_sorted_arr(root, arr)
        min_diff = float('inf')
        for i in range(1, len(arr)):
            min_diff = min(min_diff, arr[i] - arr[i-1])
        return min_diff




(230) Kth Smallest Element in a BST (Medium) NOT SOLVED ❌

(view problem)

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.


Example:

  • Input:
    root = [3,1,4,null,2], k = 1
  • Output:
    1


Solution




(98) Validate Binary Search Tree (Medium) NOT SOLVED ❌

([UUUUUURRRRRRLLL view problem])

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node's key.
  • The right subtree of a node contains only nodes with keys greater than the node's key.
  • Both the left and right subtrees must also be binary search trees.


Example:

  • Input:
    root = [2,1,3]
  • Output:
    true


Solution



Graph General


(200) Number of Islands (Medium) Solved

(view problem)

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.


Example:

  • Input:
    grid = [
 ["1","1","1","1","0"],
 ["1","1","0","1","0"],
 ["1","1","0","0","0"],
 ["0","0","0","0","0"]
  • Output:
    1


Solution
def sink_island_recursive(grid: list[list[int]], x: int, y: int, w: int, h: int) -> None:
  # End case - off grid:
  if (x < 0 or x >= w) or (y < 0 or y >= h):
    return
  # End case - already ocean:
  if grid[y][x] == '0':
    return
  
  # Recursive case (is part of island):
  grid[y][x] = '0'
  sink_island_recursive(grid, x+1, y, w, h)
  sink_island_recursive(grid, x-1, y, w, h)
  sink_island_recursive(grid, x, y+1, w, h)
  sink_island_recursive(grid, x, y-1, w, h)

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if len(grid) == 0 or len(grid[0]) == 0:
            return 0
        HEIGHT = len(grid)
        WIDTH = len(grid[0])

        num_island = 0
        for y in range(HEIGHT):
            for x in range(WIDTH):
                if(grid[y][x] == '1'):
                    num_island += 1
                    sink_island_recursive(grid, x, y, WIDTH, HEIGHT)
        return num_island




(130) Surrounded Regions (Medium) Solved

(view problem)

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.


Example:

  • Input:
    board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
  • Output:
    [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]


Solution
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        if not board or not board[0]:
            return

        h, w = len(board), len(board[0])
        # KEY:
        #   'o' = connected to edge.

        def recursive_expand_area(x: int, y: int):
            """Expands from edge cell to mark all connected as '0'."""
            if x < 0 or x >= w or y < 0 or y >= h:
                return
            if board[y][x] == 'O':
                board[y][x] = 'o'
                recursive_expand_area(x + 1, y)  # Right.
                recursive_expand_area(x - 1, y)  # Left.
                recursive_expand_area(x, y + 1)  # Down.
                recursive_expand_area(x, y - 1)  # Up.

        # STEP 1.A: Check left and right edges:
        for y in range(0, h):
            if board[y][0] == 'O':
                recursive_expand_area(0, y)
            if board[y][w - 1] == 'O':
                recursive_expand_area(w - 1, y)
        # STEP 1.A: Check top and bottom edges:
        for x in range(0, w):
            if board[0][x] == 'O':
                recursive_expand_area(x, 0)
            if board[h - 1][x] == 'O':
                recursive_expand_area(x, h - 1)

        # STEP 2: For any found island to leave on, turn to `O':
        for y in range(h):
            for x in range(w):
                if board[y][x] == 'O':
                    board[y][x] = 'X'
                elif board[y][x] == 'o':
                    board[y][x] = 'O'
        return




(133) Clone Graph (Medium) NOT SOLVED ❌

(view problem)

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

class Node {

   public int val;
   public List<Node> neighbors;

}

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.


Example:

  • Input:
    adjList = [[2,4],[1,3],[2,4],[1,3]]
  • Output:
    [[2,4],[1,3],[2,4],[1,3]]


Solution




(399) Evaluate Division (Medium) NOT SOLVED ❌

(view problem)

You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.

You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.

Return the answers to all queries. If a single answer cannot be determined, return -1.0.

Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.

Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them.


Example:

  • Input:
    equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
  • Output:
    [6.00000,0.50000,-1.00000,1.00000,-1.00000]


Solution




(207) Course Schedule (Medium) NOT SOLVED ❌

(view problem)

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.


Example:

  • Input:
    numCourses = 2, prerequisites = 1,0
  • Output:
    true


Solution




(210) Course Schedule II (Medium) NOT SOLVED ❌

(view problem)

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.


Example:

  • Input:
    numCourses = 2, prerequisites = 1,0
  • Output:
    [0,1]


Solution



Graph BFS


(909) Snakes and Ladders (Medium) Solved

([UUUUUURRRRRRLLL view problem])

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n2)]. This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board. If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next. The game ends when you reach the square n2. A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n2 do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4. Return the least number of moves required to reach the square n2. If it is not possible to reach the square, return -1.


Example:

  • Input:
    board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
  • Output:
    4


Solution
MAX_MOVES = 1000
DICE_VALUES = 6

class Cell:
  def __init__(self, move_to_square: int):    
    self.min_moves: int = MAX_MOVES
    self.move_to_idx: int = move_to_square - 1
    if move_to_square == -1:
      self.move_to_idx = -1
  
class Game:
  """Snakes and ladders game grid."""
  def __init__(self, grid: list[list[int]]):
    self.cells = []
    self.indexes_to_check = []
    WIDTH = len(grid)
    HEIGHT = len(grid[0])

    # Flatten the funny ordering of cells into a single array of cells
    # so we can think about it as a 1D array, not 2D.
    for y_virtual in range(HEIGHT):
      for x_virtual in range(WIDTH):
        y = HEIGHT - 1 - y_virtual
        x = x_virtual
        if y_virtual % 2 == 1:
          x = WIDTH - 1 - x_virtual
        self.cells.append(Cell(grid[y][x]))
  
    self.num_cells = WIDTH * HEIGHT

  def determine_min_moves(self) -> int:
    self.cells[0].min_moves = 0
    self.indexes_to_check = [0]
    while len(self.indexes_to_check) > 0:
      idx = self.indexes_to_check.pop()
      min_moves = self.cells[idx].min_moves + 1
      if min_moves >= MAX_MOVES:
        continue
      for v in range(1, DICE_VALUES + 1):
        improvement, new_idx = self.set_cell_at_idx(idx + v, min_moves)
        # TODO(anoske): Not all of these need to be checked.
        # ... if we can get to cell 3 and cell 6 in 1 move, why check cell 3?
        if improvement:
          self.indexes_to_check.append(new_idx)

    min_total_moves = self.cells[self.num_cells - 1].min_moves
    if min_total_moves == MAX_MOVES:
        min_total_moves = -1
    return min_total_moves

  def set_cell_at_idx(self, idx: int, min_moves: int) -> (bool, int):
    """Set the cell or its snake/ladder destination.
    
    Returns:
      True if new min moves for the landed upon cell.
      Index of cell landed upon (might be after a snake or ladder).
    """
    if idx >= len(self.cells):
      return False, idx
    if self.cells[idx].move_to_idx != -1:
      idx = self.cells[idx].move_to_idx

    if min_moves < self.cells[idx].min_moves:
      self.cells[idx].min_moves = min_moves
      return True, idx
    return False, idx

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        if not board or len(board) == 0 or len(board[0]) == 0:
            return -1
        game = Game(board)
        return game.determine_min_moves()




(433) Minimum Genetic Mutation (Medium) NOT SOLVED ❌

(view problem)

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

For example, "AACCGGTT" --> "AACCGGTA" is one mutation. There is also a gene bank bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank bank, return the minimum number of mutations needed to mutate from startGene to endGene. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.


Example:

  • Input:
    startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
  • Output:
    1


Solution




(127) Word Ladder (Hard) NOT SOLVED ❌

(view problem)

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList. sk == endWord Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.


Example:

  • Input:
    beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
  • Output:
    5


Solution



Trie


(208) Implement Trie (Prefix Tree) (Medium) Solved

(view problem)

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.


Example:

  • Input:
    ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
  • Output:
    [null, null, true, false, true, null, true]


Solution
NUM_LETTERS = 26

def letter_to_idx(letter: str) -> int:
    return ord(letter.lower()) - ord('a')

class TreeNode:
    def __init__(self, letter: str, end_word: bool):
        self.end_word = end_word
        self.child = None  # Lazy initialization.
    def init_child(self) -> None:
        self.child = [None] * NUM_LETTERS


class Trie:
    def __init__(self):
        self.head_node = TreeNode('-', False)

    def insert(self, word: str) -> None:
        n = self.head_node
        for i, letter in enumerate(word):
            end_word = i == len(word) - 1
            idx = letter_to_idx(letter)
            if n.child == None:
                n.init_child()
            if n.child[idx] == None:
                n.child[idx] = TreeNode(letter, end_word)
                print('letter=', letter, ' idx=', idx, ' end_word=', end_word)
            elif end_word:
                n.child[idx].end_word = True
            n = n.child[idx]

    def search(self, word: str) -> bool:
        n = self.head_node
        for i, letter in enumerate(word):
            end_word = i == len(word) - 1
            idx = letter_to_idx(letter)
            if n.child == None or n.child[idx] == None:
                return False
            elif end_word:
                return n.child[idx].end_word
            n = n.child[idx]
        return False

    def startsWith(self, prefix: str) -> bool:
        n = self.head_node
        for i, letter in enumerate(prefix):
            end_word = i == len(prefix) - 1
            idx = letter_to_idx(letter)
            if n.child == None or n.child[idx] == None:
                return False
            elif end_word:
                return True
            n = n.child[idx]
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)




(211) Design Add and Search Words Data Structure (Medium) NOT SOLVED ❌

(view problem)

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.


Example:

  • Input:
    ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]

[[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]

  • Output:
    [null,null,null,null,false,true,true,true]


Solution




(212) Word Search II (Hard) NOT SOLVED ❌

(view problem)

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.


Example:

  • Input:
    [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
  • Output:
    ["eat","oath"]


Solution



Backtracking


(17) Letter Combinations of a Phone Number (Medium) NOT SOLVED ❌

(view problem)

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.


Example:

  • Input:
    digits = "23"
  • Output:
    ["ad","ae","af","bd","be","bf","cd","ce","cf"]


Solution
DIGITS_MAPPING = [
    'abc',  # 2.
    'def',  # 3.
    'ghi',  # 4.
    'jkl',  # 5.
    'mno',  # 6.
    'pqrs',  # 7.
    'tuv',  # 8.
    'wxyz'  # 9.
]


def indexes_plus_one(indexes: list[int], digit_number_mappings: list[str], stack_letters: list[str]) -> bool:
    """Adds one to indexes (in place) as if it were a number.
    
    Returns:
        True if added, false if overflow."""
    
    for i in range(len(indexes) - 1, -1, -1):
        indexes[i] += 1
        if indexes[i] >= len(digit_number_mappings[i]):
            indexes[i] = 0
            stack_letters[i] = digit_number_mappings[i][indexes[i]]
        else:
            # print('   - i=', i, '  indexes[i]=', indexes[i] )
            stack_letters[i] = digit_number_mappings[i][indexes[i]]
            return True
    return False

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        digit_number_mappings = []
        indexes = [0] * len(digits)
        stack_letters = []
        for digit in digits:
            mapping_idx = ord(digit) - ord('2')
            digit_number_mappings.append(DIGITS_MAPPING[mapping_idx])
            stack_letters.append(DIGITS_MAPPING[mapping_idx][0])

        # Print intermediate structures:
        # print('digit_number_mappings = ', digit_number_mappings)
        # print('indexes = ', indexes)
        # print('stack_letters = ', stack_letters, '\n\n')

        combinations = []
        combinations.append( ''.join(stack_letters) )

        while indexes_plus_one(indexes, digit_number_mappings, stack_letters):
            # print(' > indexes = ', indexes)
            combinations.append( ''.join(stack_letters) )

        return combinations




(77) Combinations (Medium) NOT SOLVED ❌

(view problem)

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.


Example:

  • Input:
    n = 4, k = 2
  • Output:
    [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]


Solution




(46) Permutations (Medium) NOT SOLVED ❌

(view problem)

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.


Example:

  • Input:
    nums = [1,2,3]
  • Output:
    [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


Solution




(39) Combination Sum (Medium) NOT SOLVED ❌

(view problem)

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency

of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.


Example:

  • Input:
    candidates = [2,3,6,7], target = 7
  • Output:
    [[2,2,3],[7]]


Solution




(52) N-Queens II (Hard) NOT SOLVED ❌

(view problem)

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.


Example:

  • Input:
    n = 4
  • Output:
    2


Solution




(22) Generate Parentheses (Medium) NOT SOLVED ❌

([UUUUUURRRRRRLLL view problem])

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.


Example:

  • Input:
    n = 3
  • Output:
    ["((()))","(()())","(())()","()(())","()()()"]


Solution




(79) Word Search (Medium) NOT SOLVED ❌

(view problem)

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.


Example:

  • Input:
    board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  • Output:
    true


Solution



Divide & Conquer


(108) Convert Sorted Array to Binary Search Tree (Easy) NOT SOLVED ❌

(view problem)

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.


Example:

  • Input:
    nums = [-10,-3,0,5,9]
  • Output:
    [0,-3,9,-10,null,5]


Solution




(148) Sort List (Medium) NOT SOLVED ❌

(view problem)

Given the head of a linked list, return the list after sorting it in ascending order.


Example:

  • Input:
    head = [4,2,1,3]
  • Output:
    [1,2,3,4]


Solution




(427) Construct Quad Tree (Medium) NOT SOLVED ❌

(view problem)

Given a n * n matrix grid of 0's and 1's only. We want to represent grid with a Quad-Tree.

Return the root of the Quad-Tree representing grid.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

  • val: True if the node represents a grid of 1's or False if the node represents a grid of 0's. Notice that you can assign the val to True or False when isLeaf is False, and both are accepted in the answer.
  • isLeaf: True if the node is a leaf node on the tree or False if the node has four children.

class Node {

   public boolean val;
   public boolean isLeaf;
   public Node topLeft;
   public Node topRight;
   public Node bottomLeft;
   public Node bottomRight;

}

We can construct a Quad-Tree from a two-dimensional area using the following steps:

  1. If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop.
  2. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo.
  3. Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the wiki.

Quad-Tree format:

You don't need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val].

If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0.


Example:

  • Input:
    grid = [[0,1],[1,0]]
  • Output:
    [[0,1],[1,0],[1,1],[1,1],[1,0]]


Solution




(23) Merge k Sorted Lists (Hard) NOT SOLVED ❌

(view problem)

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.


Example:

  • Input:
    lists = [[1,4,5],[1,3,4],[2,6]]
  • Output:
    [1,1,2,3,4,4,5,6]


Solution



Kadane's Algorithm


(53) Maximum Subarray (Medium) Solved

(view problem)

Given an integer array nums, find the subarray with the largest sum, and return its sum.


Example:

  • Input:
    nums = [-2,1,-3,4,-1,2,1,-5,4]
  • Output:
    6


Solution
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        max_total = nums[0]
        total = 0
        for num in nums:
            if total < 0:
                total = 0
            total += num
            max_total = max(max_total, total)
        return max_total




(918) Maximum Sum Circular Subarray (Medium) NOT SOLVED ❌

(view problem)

Given a circular integer array nums of length n, return the maximum possible sum of a non-empty subarray of nums.

A circular array means the end of the array connects to the beginning of the array. Formally, the next element of nums[i] is nums[(i + 1) % n] and the previous element of nums[i] is nums[(i - 1 + n) % n].

A subarray may only include each element of the fixed buffer nums at most once. Formally, for a subarray nums[i], nums[i + 1], ..., nums[j], there does not exist i <= k1, k2 <= j with k1 % n == k2 % n.


Example:

  • Input:
    nums = [1,-2,3,-2]
  • Output:
    3


Solution



Binary Search


(35) Search Insert Position (Easy) Solved

(view problem)

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.


Example:

  • Input:
    nums = [1,3,5,6], target = 5
  • Output:
    2


Solution
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if not nums:
            return 0
    
        print('INPUT:  nums=', nums, ' ... target=', target)
        low, high = 0, len(nums) - 1
        
        while low <= high:
            mid = (low + high) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1
        return low




(74) Search a 2D Matrix (Medium) Solved

(view problem)

You are given an m x n integer matrix matrix with the following two properties:

Each row is sorted in non-decreasing order. The first integer of each row is greater than the last integer of the previous row. Given an integer target, return true if target is in matrix or false otherwise.

You must write a solution in O(log(m * n)) time complexity.


Example:

  • Input:
    matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
  • Output:
    true


Solution
def get_cell_value(matrix: List[List[int]], idx: int, width: int) -> int:
    x = idx % width
    y = idx // width
    return matrix[y][x]

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        
        HEIGHT, WIDTH = len(matrix), len(matrix[0])
        NUM_CELLS = HEIGHT * WIDTH

        low, high = 0, NUM_CELLS - 1
        while low < high:
            mid = (low + high) // 2
            val = get_cell_value(matrix, mid, WIDTH)
            print(' low=', low, ' mid=', mid,' (', val,') high=', high, '... target=', target)
            if val == target:
                return True
            if val < target:
                low = mid + 1
            else:
                high = mid - 1
        return get_cell_value(matrix, low, WIDTH) == target




(162) Find Peak Element (Medium) Solved

(view problem)

A peak element is an element that is strictly greater than its neighbors.

Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞. In other words, an element is always considered to be strictly greater than a neighbor that is outside the array.

You must write an algorithm that runs in O(log n) time.


Example:

  • Input:
    nums = [1,2,3,1]
  • Output:
    2


Solution
class Solution:
    def findPeakElement(self, nums: List[int]) -> int:
        if not nums:
            return 0

        low, high = 0, len(nums) - 1
        while low < high:
            mid = (low + high) // 2
            if nums[mid] < nums[mid+1]:     # Uphill to the right.
                low = mid + 1
            else:
                high = mid
        return low




(33) Search in Rotated Sorted Array (Medium) NOT SOLVED ❌

(view problem)

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.


Example:

  • Input:
    nums = [4,5,6,7,0,1,2], target = 0
  • Output:
    4


Solution




(43) Find First and Last Position of Element in Sorted Array (Medium) NOT SOLVED ❌

(view problem)

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.


Example:

  • Input:
    nums = [5,7,7,8,8,10], target = 8
  • Output:
    [3,4]


Solution




(153) Find Minimum in https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-interview-150 Sorted Array (Medium) NOT SOLVED ❌

([UUUUUURRRRRRLLL view problem])

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

  • [4,5,6,7,0,1,2] if it was rotated 4 times.
  • [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.


Example:

  • Input:
    nums = [3,4,5,1,2]
  • Output:
    1


Solution




(4) Median of Two Sorted Arrays (Hard) NOT SOLVED ❌

(view problem)

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).


Example:

  • Input:
    nums1 = [1,3], nums2 = [2]
  • Output:
    2.00000


Solution



Heap


(215) Kth Largest Element in an Array (Medium) Solved

(view problem)

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?


Example:

  • Input:
    nums = [3,2,1,5,6,4], k = 2
  • Output:
    5


Solution
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        if not nums:
            return 0
        smallest_x = len(nums) - k + 1
        if smallest_x < 1:
            return 0

        min_val = float('inf')
        max_val = -float('inf')
        for num in nums:
            min_val = min(min_val, num)
            max_val = max(max_val, num)

        if k == 1:
            return max_val
        if smallest_x == 1:
            return min_val

        while min_val < max_val:
            mid = (max_val + min_val) // 2
            num_equal = 0
            num_less = 0
            for num in nums:
                if num == mid:
                    num_equal += 1
                elif num < mid:
                    num_less += 1

            num_equal_or_less = num_equal + num_less
            if smallest_x <= num_less:
                max_val = mid
            elif smallest_x > num_equal_or_less:
                min_val = mid
            else:
                return mid
        return min_val




(502) IPO (Hard) NOT SOLVED ❌

(view problem)

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.


Example:

  • Input:
    k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
  • Output:
    4


Solution




(373) Find K Pairs with Smallest Sums (Medium) Solved

(view problem)

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.


Example:

  • Input:
    nums1 = [1,7,11], nums2 = [2,4,6], k = 3
  • Output:
    [[1,2],[1,4],[1,6]]


Solution




(295) Find Median from Data Stream (Hard) NOT SOLVED ❌

(view problem)

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

  • For example, for arr = [2,3,4], the median is 3.
  • For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

  • MedianFinder() initializes the MedianFinder object.
  • void addNum(int num) adds the integer num from the data stream to the data structure.
  • double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.


Example:

  • Input:
    ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []]
  • Output:
    [null, null, null, 1.5, null, 2.0]


Solution



Bit Manipulation


(67) Add Binary (Easy) Solved

(view problem)

Given two binary strings a and b, return their sum as a binary string.


Example:

  • Input:
    a = "11", b = "1"
  • Output:
    "100"


Solution
def binary_str_to_int(s: str) -> int:
    if not s:
        return 0
    total = 0
    for digit in s:
        val = 0
        if digit == '1':
            val = 1
        total = (total * 2) + val
    return total

def int_to_binary_string(value: int) -> str:
    if value == 0:
        return '0'
    digits_arr = []
    while value > 0:
        digits_arr.append(str(value % 2))  # Add remainder.
        value = value // 2
    digits_arr.reverse()
    return ''.join(digits_arr)

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        a_val = binary_str_to_int(a)
        b_val = binary_str_to_int(b)
        return int_to_binary_string(a_val + b_val)
        # TODO(noske): See if just iterate from the back of the array
        # and doing a 'carry-over' num is faster.




(190) Reverse Bits (Easy) Solved

(view problem)

Reverse bits of a given 32 bits unsigned integer.

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.


Example:

  • Input:
    n = 00000010100101000001111010011100
  • Output:
    964176192 (00111001011110000010100101000000)


Solution
class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for _ in range(32):
            result <<= 1           # Left shift result
            result |= n & 1        # Bitwise OR result with the rightmost bit of n
            n >>= 1                # Right shift n to process the next bit
        return result




(191) Number of 1 Bits (Easy) Solved

(view problem)

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3.


Example:

  • Input:
    n = 00000000000000000000000000001011
  • Output:
    3


Solution
class Solution:
    def hammingWeight(self, n: int) -> int:
        # print('n=', n, ' -> ', bin(n))
        num_ones = 0
        while n > 0:
            num_ones += n & 1  # Mask on last bit.
            n >>= 1            # Right shift.
        return num_ones




(136) Single Number (Easy) Solved

(view problem)

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.


Example:

  • Input:
    nums = [2,2,1]
  • Output:
    1


Solution
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result = result ^ num
        return result




(137) Single Number II (Medium) Solved

(view problem)

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.


Example:

  • Input:
    nums = [2,2,3,2]
  • Output:
    3


Solution
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        one, two, three = 0, 0, 0
        for num in nums:
            # `two` keeps the bits which appear twice.
            two |= one & num
            # `one` keeps the bits which appear for the first time.
            one ^= num
            # `three` represents whether one bit has appeared three times.
            three = one & two
            # if one bit has appeared three times, we clear the 
            # corresponding bits in both `one` and `two`.
            one &= ~three
            two &= ~three
        return one




(201) Bitwise AND of Numbers Range (Medium) NOT SOLVED ❌

(view problem)

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.


Example:

  • Input:
    left = 5, right = 7
  • Output:
    4


Solution



Math


(9) Palindrome Number (Easy) Solved

(view problem)

Given an integer x, return true if x is a palindrome, and false otherwise.


Example:

  • Input:
    x = 121
  • Output:
    true


Solution
class Solution:
    def isPalindrome(self, x: int) -> bool:
        x_str = str(x)
        mid = len(x_str) // 2
        for i in range(0, mid):
            if x_str[i] != x_str[len(x_str) - i - 1]:
                return False
        return True




(66) Plus One (Easy) Solved

(view problem)

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.

Increment the large integer by one and return the resulting array of digits.


Example:

  • Input:
    [1,2,3]
  • Output:
    [1,2,4]


Solution
class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        new_digits = []
        to_add = 1
        for i in range(len(digits) - 1, -1, -1):
            new_digits.append( (digits[i] + to_add) % 10 )
            if to_add > 0 and digits[i] < 9:
                to_add = 0
        if to_add == 1:
            new_digits.append(1)
        new_digits.reverse()
        return new_digits




(172) Factorial Trailing Zeroes (Medium) NOT SOLVED ❌

(view problem)

Given an integer n, return the number of trailing zeroes in n!.

Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.


Example:

  • Input:
    n = 3
  • Output:
    0


Solution




(69) Sqrt(x) (Easy) Solved

(view problem)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.


Example:

  • Input:
    x = 4
  • Output:
    2


Solution
class Solution:
    def mySqrt(self, x: int) -> int:
        if x < 2:
            return x
        if x == 2:
            return 1

        low, high = 1, x // 2  # Square root is always less than half.
        while low <= high:
            mid = (low + high) // 2
            square = mid * mid
            if square == x:
                return mid
            if square < x:
                low = mid + 1
            else:
                high = mid - 1
        if high * high < x:
            return high
        return low




(50) Pow(x, n) (Medium) Solved

(view problem)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).


Example:

  • Input:
    x = 2.00000, n = 10
  • Output:
    1024.00000


Solution
class Solution:
    def myPow(self, x: float, n: int) -> float:
        # Base cases:
        if n == 0:
            return 1
        if n < 0:
            x = 1 / x
            n = -n

        # Recursive function to implement the logic:
        def pow_recursive(x, n):
            """We reduce the number of multiplications using the properties of exponents.
            
            For instance: x^8 is the same as (x^4) * (x^4).
            > 3^4   (81) = 3^2 (9)  * 3^2 (9)
            > 2^8  (256) = 2^4 (16) * 2^4 (16)
            > 2^5.5 (45.255) = 2^2 (4) * 2^2 (4) [16] * 2.75 (5.5/2)
            Instead of multiplying x by itself 8 times, we can square x^4 once to get x^8.
            """
            if n == 0:
                return 1
            half = pow_recursive(x, n // 2)
            if n % 2 == 0:
                return half * half
            else:
                return half * half * x
        return pow_recursive(x, n)




(149) Max Points on a Line (Hard) NOT SOLVED ❌

(view problem)

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.


Example:

  • Input:
    points = [[1,1],[2,2],[3,3]]
  • Output:
    3


Solution



1D DP


(70) Climbing Stairs (Easy) NOT SOLVED ❌

(view problem)

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?


Example:

  • Input:
    n = 2
  • Output:
    2


Solution




(198) House Robber (Medium) NOT SOLVED ❌

(view problem)

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.


Example:

  • Input:
    nums = [1,2,3,1]
  • Output:
    4


Solution




(139) Word Break (Medium) NOT SOLVED ❌

(view problem)

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.


Example:

  • Input:
    s = "leetcode", wordDict = ["leet","code"]
  • Output:
    true


Solution




(322) Coin Change (Medium) NOT SOLVED ❌

(view problem)

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.


Example:

  • Input:
    coins = [1,2,5], amount = 11
  • Output:
    3


Solution




(300) Longest Increasing Subsequence (Medium) NOT SOLVED ❌

([UUUUUURRRRRRLLL view problem])

Given an integer array nums, return the length of the longest strictly increasing subsequence.


Example:

  • Input:
    nums = [10,9,2,5,3,7,101,18]
  • Output:
    4


Solution



Multidimensional DP


(120) Triangle (Medium) NOT SOLVED ❌

(view problem)

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.


Example:

  • Input:
    triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
  • Output:
    11


Solution




(64) Minimum Path Sum (Medium) NOT SOLVED ❌

(view problem)

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.


Example:

  • Input:
    grid = [[1,3,1],[1,5,1],[4,2,1]]
  • Output:
    7


Solution




(63) Unique Paths II (Medium) NOT SOLVED ❌

(view problem)

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.

Return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The testcases are generated so that the answer will be less than or equal to 2 * 109.


Example:

  • Input:
    obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
  • Output:
    2


Solution




(5) Longest Palindromic Substring (Medium) NOT SOLVED ❌

(view problem)

Given a string s, return the longest palindromic substring in s.


Example:

  • Input:
    s = "babad"
  • Output:
    "bab"


Solution




(97) Interleaving String (Medium) NOT SOLVED ❌

(view problem)

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m substrings respectively, such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm


Example:

  • Input:
    s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
  • Output:
    true


Solution




(72) Edit Distance (Medium) NOT SOLVED ❌

(view problem)

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • Replace a character


Example:

  • Input:
    word1 = "horse", word2 = "ros"
  • Output:
    3


Solution




(123) Best Time to Buy and Sell Stock III (Hard) NOT SOLVED ❌

(view problem)

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).


Example:

  • Input:
    prices = [3,3,5,0,0,3,1,4]
  • Output:
    6


Solution




(188) Best Time to Buy and Sell Stock IV (Hard) NOT SOLVED ❌

(view problem)

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).


Example:

  • Input:
    k = 2, prices = [2,4,1]
  • Output:
    2


Solution




(221) Maximal Square (Medium) NOT SOLVED ❌

(view problem)

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.


Example:

  • Input:
    matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
  • Output:
    4


Solution



See Also


Links