Dsa Posts
-
Matrices
Date: 2024-09-28
Matrices
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
list_of_zeros = []
width = len(matrix)
height = len(matrix[0])
# find the 0s in the matrix
for x in range(0, width):
for y in range(0, height):
if matrix[x][y] == 0:
# what should we do when we find a 0?
# naive approach, store loc in a list, and then once we've scanned the matrix, go back and set the rows/cols for that location to 0
list_of_zeros.append([x, y])
for loc_of_zero in list_of_zeros:
def set_row_col_zero(loc):
x = loc[0]
y = loc[1]
# set row to zero
for r in range(0, width):
matrix[r][y] = 0
# set col to zero
for c in range(0, height):
matrix[x][c] = 0
set_row_col_zero(loc_of_zero)
- Key insight: Find the 0 in our matrix and store the location in a list. Once we've gone through our matrix, go back to our list and set its entire row and column to zero. I went with a naive, space inefficient approach for now, but will keep thinking about how to do this in O(m+n) and eventually constant space...
Date: 2024-09-27
Stacks
class MyQueue(object):
def __init__(self):
self.stack_1 = []
self.stack_2 = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack_1.append(x)
def pop(self):
"""
:rtype: int
"""
while self.stack_1:
self.stack_2.append(self.stack_1.pop())
popped_value = self.stack_2.pop()
while self.stack_2:
self.stack_1.append(self.stack_2.pop())
return popped_value
def peek(self):
"""
:rtype: int
"""
return self.stack_1[0]
def empty(self):
"""
:rtype: bool
"""
return len(self.stack_1) == 0
- Key insight: Pop elements from stack 1 over to stack 1, pop the top of stack 2 to get our queue pop behavior, then bring everything from stack 2 back to stack 1.
Date: 2024-09-26
Strings
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: int
"""
pairs = set()
counter = 0
for c in s:
if c not in pairs:
pairs.add(c)
elif c in pairs:
pairs.remove(c)
counter += 2
if pairs:
counter += 1
# a string that can't be a palindrome will just return 0
return counter
- Key insight: When working with palindromes, look for a way to track pairs, and one odd character. For this problem, we leverage the notion that valid palindrome has pairs of characters, and at most one non-pair. We use a set to find pairs and if we have one, add two to our counter. At the end, if we have any more characters in our set, just add 1 to our counter. I wasn't sure how leetcode wanted to handle a string that couldn't make a palindrome, but I guess returning 0 makes sense in this context.
Date: 2024-09-26
Arrays
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
complement_index = {}
for i, n in enumerate(nums):
print(i, n)
complement = target - n
print(complement)
complement_index[complement] = i
for i, n in enumerate(nums):
if n in complement_index and i != complement_index[n]:
print(n)
return [i, complement_index[n]]
- Key insight: Figure out the complement for each value in nums, and then store that complement in a dictionary, wit the index of that value. After, iterate through nums again and see if n is in our complement_index dict (which means we found a complement). If so, return our current index of the complement, plus the index of the original value from our first scan. Make sure that both of these indexes aren't the same value.