03.21.23

238. Product of Array Except Self

Difficulty: Medium

Goal: given an array of numbers, return an array of the same length in which each position contains the product of all the numbers aside from itself.

I wasn't able to understand the naive solution for this one so I skipped straight to the optimized implementation.

Algorithm: This algorithm works using two passes over the array and only requires memory for the output array and a temp value. Every member of our output array will be the product of the members before it and the members after. So what we can do is first calculate the "before" values in one pass, and then in the next one iterate over those to calculate the "after" ones.

Example input: [2, 5, 3]

Initialize equal length array of 1's and a temp int = 1
```
[1, 1, 1], t = 1
```
Iterate LTR from second index to last index:
1. Set temp to itself times the index before in our input
2. Set our result index to temp
```
[1, 1, 1], t = 2
[1, 2, 1], t = 10
[1, 2, 10]
```
Iterate RTL from second to last index to first index:
1. Set result index to itself times temp
2. set temp equal to itself times current index in nums
```
[1, 2, 10], t = 3
[1, 6, 10], t = 15
[15, 6, 10]
```

Python implementation:

def productExceptSelf(self, nums: List[int]) -> List[int]
    ceil = len(nums)
    hold = [1] * ceil

    temp = 1
    for i in range(1, ceil):
        temp*= nums[i-1]
        hold[i] = temp

    temp = 1
    for i in range(ceil-1, -1, -1):
        hold[i] *= temp
        temp *= nums[i]

    return hold

36. Valid Sudoku

Difficulty: Medium

Goal: check validity of a partially solved sudoku board

Naive solution: check every row, every column, every square

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # check row dupes
        columns = [[] for _ in range(9)]
        for row in board:
            newrow = [i for i in row if i != '.']
            if not len(newrow) == len(set(newrow)):
                return False

            # populate cols
            for i in range(len(row)):
                columns[i] += row[i]

        # check column dupes
        for col in columns:
            newcol = [i for i in col if i != '.'] 
            if not len(newcol) == len(set(newcol)):
                return False

        # check square dupes
        coords = [(0,2), (3,5), (6,8)]
        for i in coords:
            for j in coords:
                nums = []
                for k in range(j[0], j[1]+1):
                    nums += [l for l in board[k][i[0]:i[1]+1] if l != '.']
                if not len(nums) == len(set(nums)):
                    return False

        return True

Optimized solution: this optimized allows us to only make one pass over each point on the board. we check each coordinate one at a time, seeing if we can find it in our dictionaries. we use integer division to find the square a coordinate belongs to -- this is the key to the simplicity of this algorithm. the board is broken up into 3 sections each way, so if we divide every coordinate by 3, we'll be given the square it's in. for example, (8, 2) is in the top right square. 8//3 = 2, 2//3 = 0.

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = collections.defaultdict(set)
        cols = collections.defaultdict(set)
        squares = collections.defaultdict(set)
        for row in range(9):
            for col in range(9):
                val = board[row][col]
                if val == '.':
                    continue
                if (val in rows[row] or
                    val in cols[col] or
                    val in squares[(row//3, col//3)]):
                    return False
                rows[row].add(val)
                cols[col].add(val)
                squares[(row//3, col//3)].add(val)
        return True

11. Container With Most Water

Difficulty: Medium

Goal: given a list of possible containers, find container that could contain the most water

implemented optimized solution before naive solution (if one even exists). it's the little wins!

Algorithm: two pointers algorithm. have one pointer start at beginning and the other at the end. in a loop, move first one forward if it's a smaller line than second, otherwise move second one back. calculate container size at every step keeping the max.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        p1 = 0
        p2 = len(height) -1
        amount = 0
        while p1 <= p2:
            newamount = min(height[p1], height[p2]) * (p2-p1)
            if newamount > amount:
                amount = newamount
            if height[p1] < height[p2]:
                p1 += 1
            else:
                p2 -= 1
        return amount