Dsa Posts
-
Matrices
Date: 2024-09-28
- 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...
-
Stacks
Date: 2024-09-27
- 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.
-
Strings
Date: 2024-09-26
- 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.
-
Arrays
Date: 2024-09-26
- 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.
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)
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
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
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]]