# SE103 Week 11 Review
## [Unique Paths III](https://leetcode.com/problems/unique-paths-iii/)

class Solution:
    res = 0

    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        startingPoint = self.findStartingPoint(grid)
        self.uniquePathsIIIHelper(grid, startingPoint[0], startingPoint[1])
        return self.res
        
    def uniquePathsIIIHelper(self, grid, x, y):
        width, height = len(grid[0]), len(grid)
        if x < 0 or y < 0 or x >= width or y >= height or grid[y][x] == -1:
            return
        if grid[y][x] == 2:
            for i in range(height):
                for j in range(width):
                    if grid[i][j] == 0:
                        return
            self.res += 1
            return
            
        grid[y][x] = -1
        self.uniquePathsIIIHelper(grid, x - 1, y)
        self.uniquePathsIIIHelper(grid, x + 1, y)
        self.uniquePathsIIIHelper(grid, x, y - 1)
        self.uniquePathsIIIHelper(grid, x, y + 1)
        grid[y][x] = 0
    
    def findStartingPoint(self, grid):
        for y in range(len(grid)):
            for x in range(len(grid[0])):
                if grid[y][x] == 1:
                    return (x, y)

## [Path with Max Gold](https://leetcode.com/problems/path-with-maximum-gold/)

class Solution:
    maxGoldFound = 0
    
    def getMaximumGold(self, grid: List[List[int]]) -> int:
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                self.dfs(grid, i, j, 0)
        return self.maxGoldFound

    def dfs(self, grid, i, j, currGold):
        width, height = len(grid[0]), len(grid)
        if i < 0 or j < 0 or i >= height or j >= width or grid[i][j] == 0:
            return
        goldInCell = grid[i][j]
        totalGold = currGold + goldInCell
        if totalGold > self.maxGoldFound:
            self.maxGoldFound = totalGold
        grid[i][j] = 0
        self.dfs(grid, i - 1, j, totalGold)
        self.dfs(grid, i + 1, j, totalGold)
        self.dfs(grid, i, j + 1, totalGold)
        self.dfs(grid, i, j - 1, totalGold)
        grid[i][j] = goldInCell

## [Unique Paths](https://leetcode.com/problems/unique-paths/)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        paths = [[0 for _ in range(m)] for _ in range(n)]
        paths[0][0] = 1
        for i in range(n):
            for j in range(m):
                if i == 0 and j == 0:
                    continue
                pathsFromAbove = 0 if i - 1 < 0 else paths[i - 1][j]
                pathsFromLeft = 0 if j - 1 < 0 else paths[i][j - 1]
                paths[i][j] = pathsFromAbove + pathsFromLeft
        return paths[n - 1][m - 1]

## [Advantage Shuffle](https://leetcode.com/problems/advantage-shuffle/)

from collections import deque, defaultdict

class Solution:
    def advantageCount(self, nums1: List[int], nums2: List[int]) -> List[int]:
        sortedNums1 = sorted(nums1)
        sortedNums2 = sorted(nums2)
        assigned = defaultdict(deque)
        unassigned = deque()
        
        currBIndex = 0
        for a in sortedNums1:
            b = sortedNums2[currBIndex]
            if a > b:
                assigned[b].append(a)
                currBIndex += 1
            else:
                unassigned.append(a)
        
        res = []
        for b in nums2:
            if len(assigned[b]) > 0:
                res.append(assigned[b].pop())
            else:
                res.append(unassigned.pop())
        return res