LeetCode Easy
I’ve always struggled with LeetCode problems, so I’ve set a goal to tackle one LeetCode problem every day. These will be from the easy section. I’ll keep updating my posts with my progress. The day I don’t need to post anymore will be the day I can breeze through lc-problems with no trouble.
Problem1: Two Sum
Given an array of integers (nums) and an integer (target), return the indices of the two numbers that add up to the target.
Example:
nums = [2, 7, 11, 15]
target = 9
Output: [0, 1] // Because 2 + 7 = 9
Constraints
- You may assume that each input would have exactly one solution.
- You may not use the same element twice.
My thoughts
- 1: Brute force it, for i in num, we use i+(i+1) to match the target, if unmatch then move on to check i+1+(i+1+1)…until target match.
- 2: loop the array, then target - num = complement, we check if complment is seen in the dictionary, if seen we get the current array index and the index of the seen dictionary. As we loop through the array, we store each number as a key in the hashmap and its index as the value.For each number, we calculate the complement needed to reach the target. Then we simply check if that complement already exists as a key in our hashmap. If it does, we’ve found our pair!
Smart way
Python:
def two_sum(nums, target):
seen = {} # Create an empty hashmap (dictionary)
for index, num in enumerate(nums): # enumerates assgin pairs, turns your nums list into pairs
# like this:(0, 2) index 0, value 2 ; (1, 7) index 1, value 7
complement = target - num
if complement in seen: # The complement is found...
return [seen[complement], index] //get the 2 index
//If the complement is already present as a key(key in hashmap is like words, like real stuff, in this case is the number itself) in the seen hashmap, it means its found. Return the index of the current number(index) and the stored index(stored value in hashmap seen[complement]). remember the stored value its the index
seen[num] = index # store the current num as a key and its index as the value in our seen dictionary
return None # This means no solution was found
why this work: By storing numbers as keys, we can quickly check if the complement we need has already been seen during our loop.
Brute Froce Way
def two_sum_brute_force(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)): # Start inner loop from next index
if nums[i] + nums[j] == target:
return [i, j]
return None # No solution found
Space Complexity
Brute Force Time Complexity: O(n^2). We have nested loops, each going through potentially all elements.
Hashmap Approach Time Complexity: O(n). On average, we loop through the array once, and hashmap operations are fast.
Problem2: Palindrome Number
Determine if an integer is a palindrome, where it reads the same backward as forward.
Example:
-
Input: 121
Output: true -
Input: -121 Output: false (negative numbers are not palindromes)
-
Input: 10 Output: false
Constraints
You shouldn’t convert the integer into a string to solve this problem. Think about how you can work with the number itself mathematically.
My thoughts Using % rio get the last digit , and division // by 10 to shift the digt, build a rever one and compare it with the original
Python Smart Solution
def is_palindrome(x):
if x < 0:
return False
original_num = x # original number x
reversed_num = 0 # Initialize the reversed number
// extract digits and build reversed_num
while x > 0: # Loop as long as the number is positive
last_digit = x % 10 # Extract the last digit
reversed_num = reversed_num * 10 + last_digit // shhifting the previous number to the left(*10)
x = x // 10 # Remove the last digit from the original number
# Handle potential middle digit in reversed_num
if original_num // 10 == reversed_num // 10: //removes the middle digit if the original has odd len
return True
else:
return False
Python no Opt Solution previous solustion include an optimization where we only need to reverse about half of the digits to determine if a number is a palindrome. Reseaon why Opt works: Odd number of digits: The middle digit doesn’t affect if it’s a palindrome (e.g., in ‘12321’, the ‘3’ doesn’t matter). Even number of digits: All digits must fully match when reversed.
// not Opt veriosn fully reversed number first and then compare it to the original:
def is_palindrome(x):
if x < 0:
return False
original_num = x
reversed_num = 0
while x > 0:
last_digit = x % 10
reversed_num = reversed_num * 10 + last_digit
x = x // 10 // its same as Opt version untill here
//The loop continues until the entire number is reversed.
# Comparison after building the complete reversed number
return original_num == reversed_num
Problem3: Roman to Integer
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 |
They are usually written largest to smallest from left to right. However, the numeral for four is not IIII, but rather IV. The six subtractive combinations are:
- IV (5 - 1 = 4)
- IX (10 - 1 = 9)
- XL (50 - 10 = 40)
- XC (100 - 10 = 90)
- CD (500 - 100 = 400)
- CM (1000 - 100 = 900)
Given a roman numeral, convert it to an integer.
Example
-
Input: “III” Output: 3
-
Input: “LVIII” Output: 58 (L = 50, V= 5, III = 3)
-
Input: “MCMXCIV” Output: 1994 (M = 1000, CM = 900, XC = 90 and IV = 4)
Hint
- Think about using a dictionary (hashmap) to store the mappings between the Roman numeral symbols and their corresponding integer values.
- Process the Roman numeral string from left to right.
- If the current symbol’s value is greater than or equal to the value of the previous symbol, you simply add its value to your running total.
- However, if the current symbol’s value is less than the previous symbol’s value, it means you have one of the subtractive cases (like ‘IV’ or ‘IX’).
- Instead of checking for every possible subtractive case individually, we store the valid subtractive pairs in a list or a set. subtractive_pairs = [“IV”, “IX”, “XL”, “XC”, “CD”, “CM”]
Specific Example: In the Roman numeral “MCMXCIV”:
- M (1000) -> Add to the total
- CM (900) -> Since ‘C’ is smaller than ‘M’, subtract this from the total
- XC (90) -> Likewise, subtract
- IV (4) -> Subtract
Python Solution
def roman_to_integer(s):
symbol_values = { # Create dictionary of Roman symbol values
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
subtractive_pairs = ["IV", "IX", "XL", "XC", "CD", "CM"]
# Instead of checking for every possible subtractive case individually, we store the valid subtractive pairs in a list or a set, so that we could just compare it
total = 0 # Count for total value
i = 0
while i < len(s): # Loop through the Roman numeral string
if i + 1 < len(s):
next_symbol = s[i + 1]
else:
next_symbol = "" # At the last symbol, so set to empty string
two_symbols = s[i] + next_symbol # like MD
# Combine the current and next symbols into a string
if two_symbols in subtractive_pairs:
total += symbol_values[next_symbol] - symbol_values[s[i]] # Subtract value of the first symbol from the second
i += 2 # Move ahead two positions
else:
total += symbol_values[s[i]] # Add value of the single symbol
i += 1 # Move ahead one position
return total
Problem4: Fizz Buzz
Write a program that prints the numbers from 1 to 100. But for multiples of three, print “Fizz” instead of the number, and for the multiples of five, print “Buzz”. For numbers which are multiples of both three and five, print “FizzBuzz”.
Example:
Output:
1
2
Fizz
4
Buzz
Fizz
...
Considerations
15 % 3 == 0// 15 is divisible by 3-
12 % 5 == 0// 12 is divisible by 5 - Check for both 3 and 5: If the number is divisible by both 3 and 5, print “FizzBuzz”.
- Check for 3: If the number is divisible by 3, print “Fizz”.
- Check for 5: If the number is divisible by 5, print “Buzz”.
- Default: If none of the above conditions are true, print the number itself.
Python Solution
def fizz_buzz():
for num in range(1, 101): # Loop through the numbers
if num % 3 == 0 and num % 5 == 0: # Check divisibility by 3 and 5
print("FizzBuzz")
elif num % 3 == 0: # Check divisibility by 3
print("Fizz")
elif num % 5 == 0: # Check divisibility by 5
print("Buzz")
else: # Not divisible by 3 or 5
print(num)
Important Note: The order of the if and elif conditions matters! You have to check for “FizzBuzz” (divisible by both 3 and 5) first.
Problem5: Contains Duplicate:
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
- Input: nums = [1,2,3,1]
- Output: true (1 appears twice)
Example 2:
- Input: nums = [1,2,3,4]
- Output: false (all elements are unique)
Example 3:
- Input: nums = [1,1,1,3,3,4,3,2,4,2]
- Output: true (many duplicates!)
Hint: Consider using a hashmap (dictionary) to keep track of the numbers you’ve seen so far.
Python Solution
def contains_duplicate(nums):
seen = set()
for num in nums
if num in seen
return True
else
seen.add(num)
return False
Problem6: Two Sum II - Input Array Is Sorted
Given a sorted array of integers (nums) and a target value, find the indices of the two numbers that add up to the target. You can assume there’s exactly one solution, and you cannot use the same element twice.
Note: The array is 1-indexed, meaning the first element has an index of 1.
Example 1:
- Input: nums = [2, 7, 11, 15], target = 9
- Output: [1, 2] (Because 2 + 7 = 9)
Example 2:
- Input: nums = [2, 3, 4], target = 6
- Output: [1, 3] (Because 2 + 4 = 6)
Considerations
- Sorted Array (Important): The fact that the array is sorted gives us a potential advantage. Think about how you might take advantage of that.
- Hashmaps: Can a hashmap still be helpful in this scenario?
Python Solution
def two_sum_sorted(nums, target):
seen={}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement]+1, i+1]
seen[num]=i
return None
Problem7: Best Time to Buy and Sell Stock
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 1:
- Input: prices = [7,1,5,3,6,4]
- Output: 5
- Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Example 2:
- Input: prices = [7,6,4,3,1]
- Output: 0
- Explanation: In this case, no transaction is done, i.e. max profit = 0.
Considerations:
- Think about how you would track the minimum price seen so far.
- How can you continuously update your potential maximum profit?
min_price_so_far: The lowest price you’ve encountered up to that point.max_profit: The best profit you’ve been able to achieve so far.
Python Solution
def max_profit(prices):
min_price = 1000000 # A very large starting point for the minimum
best_profit = 0
for current_price in prices:
# Did we find a new minimum buying price?
if current_price < min_price:
min_price = current_price
# Could selling today make a better profit?
potential_profit = current_price - min_price
if potential_profit > best_profit:
best_profit = potential_profit
return best_profit
def max_profit(prices):
min_price_so_far = float('inf') # this is like setting the min price to infint, so that
# it always start with the first one in array
max_profit = 0
for price in prices:
min_price_so_far = min(min_price_so_far, price) # compare and get the min, its price everytime
max_profit = max(max_profit, price - min_price_so_far)
return max_profit
Problem8: Valid Sudoku
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.
A partially filled Sudoku board (which is valid):
[
["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"]
]
Considerations
- Data Structures: You might find it helpful to use sets or hashmaps to keep track of numbers you’ve already seen in a row, column, or sub-box.
- Organizing Your Checks: Think systematically about how to iterate and check rows, columns, and the 3x3 sub-boxes.
Thoughts nestes loop for col and row, might need a set for subbox and row and col each. use int div // divide cells into 3X3.
Python Solution
def is_valid_sudoku(board):
def is_valid(row, col, num):
# Check the row
for i in range(9):
if board[row][i] == num:
return False
# Check the column
for i in range(9):
if board[i][col] == num:
return False
# Check the 3x3 sub-box.
subbox_row_start = (row // 3) * 3
subbox_col_start = (col // 3) * 3
for i in range(subbox_row_start, subbox_row_start + 3):
for j in range(subbox_col_start, subbox_col_start + 3):
if board[i][j] == num:
return False
return True
# Main Validation Logic
for row in range(9):
for col in range(9):
if board[row][col] != '.': # Check if cell has a number
num = board[row][col]
if is_valid(row, col, num) == False: # Check for invalid
return False # Invalid placement found
return True # Valid if we pass all the checks
Python OPT Solution
def is_valid_sudoku(board):
def is_valid(row, col, num):
# Optimized row and column checks, in just one loop
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
subbox_row_start = (row // 3) * 3
subbox_col_start = (col // 3) * 3
for i in range(subbox_row_start, subbox_row_start + 3):
for j in range(subbox_col_start, subbox_col_start + 3):
if board[i][j] == num:
return False
return True
# Main Validation Logic (using sets for additional optimization)
# create unique strings (like "(2)5" to represent seeing the number '5' in row 2) for storing in the seen set
seen = set() # but use set consume memory
for row in range(9):
for col in range(9):
if board[row][col] != '.':
num = board[row][col]
check_str = f"({row}){num}"
# Check row-"(2)5" to represent seeing the number '5' in row 2
if check_str in seen: return False
seen.add(check_str)
check_str = f"{num}({col})" # Check column
if check_str in seen: return False
seen.add(check_str)
check_str = f"//({row // 3})({col // 3}){num}" # Check subbox
if check_str in seen: return False
seen.add(check_str)
return True
Problem9: Reverse Integer
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.
Example 1:
- Input: x = 123
- Output: 321
Example 2:
- Input: x = -123
- Output: -321
Example 3:
- Input: x = 120
- Output: 21
Python No OPT Solution
def reverse_integer(x)
is_negative=False
if x<0:
is_negative = True
x= -x
reverse_number=0
while x>0:
last_digit = x%10
reverse_number = reverse_number * 10 + last_digit
x= x//10
if is_negative:
reverse_number = -reverse_number
return rever_number
Python OPT Version
def reverse_integer(x):
is_negative = x < 0 # Store if the number is negative
x = abs(x) # Work with the absolute value
reversed_num = 0
while x > 0:
last_digit = x % 10 # Extract the last digit
reversed_num = reversed_num * 10 + last_digit # Build the reversed number
x //= 10 # Remove the last digit from the original number
# Check for overflow (adjust limits for 32-bit integers)
if reversed_num > 2**31 - 1:
return 0
return reversed_num if not is_negative else -reversed_num # Add the sign back
Python OPT Version with String conversion
def reverse_integer(x):
is_negative = x < 0
str_x = str(x)
if is_negative:
str_x = str_x[1:] # Remove the negative sign
reversed_str = str_x[::-1]
reversed_int = int(reversed_str)
# Overflow Check (adjust limits for 32-bit integers)
if reversed_int > 2**31 - 1 or reversed_int < -2**31:
return 0
return reversed_int if not is_negative else -reversed_int
Problem 10
Given two strings s and t, return true if t is an anagram of s, and false otherwise. An anagram is a wordor phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
Examples:
- Input: s = “anagram”, t = “nagaram”
- Output: true
- Input: s = “rat”, t = “car”
- Output: false
Approaches
There are a few ways to tackle this problem:
-
Sorting: Sort the characters in both strings and compare them. If they are anagrams, the sorted strings will be identical.
-
Hashmap (Dictionary): Count the occurrences of each character in the first string. Decrement the count for each character in the second string. If all counts reach zero, it’s a valid anagram.
Python HashMap Solution
def is_anagram(s, t):
if len(s) != len(t): # Quick check for length mismatch, obvious
return False
char_counts = {} # to store the frequency of characters(the value)
for char in s:
if char in char_counts:
char_counts[char] += 1 # its already in the hashmap, and we add count 1
else:
char_counts[char] = 1 # if not in map, it appears only 1 time, init
for char in t:
if char in char_counts:
char_counts[char] -= 1 # Decrement the count
if char_counts[char] < 0: # means t have extra char
return False
else:
return False #char not found in s
for count in char_counts.values():
if count ! =0:
return False
return True
Python Sorting Solution, kind of cheating
def is_anagram(s, t):
if len(s) != len(t):
return False # Length mismatch is an immediate giveaway
return sorted(s) == sorted(t)