Given a square grid of integers arr, a falling path with non-zero shifts is a choice of exactly one element from each row of arr, such that no two elements chosen in adjacent rows are in the same column.
Return the minimum sum of a falling path with non-zero shifts.
 
Example 1:
Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

 
Constraints:

1 <= arr.length == arr[i].length <= 200
-99 <= arr[i][j] <= 99

Difficulty: interview

Starter code:

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [0] * len(arr[0])
        for r, row in enumerate(arr):
            minNb = min(dp)
            min1 = dp.index(minNb)
            dp[min1] = float('inf')
            min2 = dp.index(min(dp))
            dp[min1] = minNb
            
            for c in range(len(row)):
                if c != min1:
                    row[c] += dp[min1]
                else:
                    row[c] += dp[min2]
                #row[c] += min(dp[:c]+dp[c+1:])
            dp = row[:]
        return min(dp)

class Solution(object):
    def minFallingPathSum(self, arr):
        \"\"\"
        :type arr: List[List[int]]
        :rtype: int
        \"\"\"
        m, n = len(arr), len(arr[0])
        i = 1
        while i < m:
            a = arr[i - 1][:]
            min1 = a.index(min(a))
            a[min1] = float('inf')
            min2 = a.index(min(a))
            a = arr[i - 1]
            for j in range(n):
                if j == min1:
                    arr[i][j] += a[min2]
                else:
                    arr[i][j] += a[min1]
            i += 1
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(1, len(arr)):
            r = heapq.nsmallest(2, arr[i - 1])
            for j in range(len(arr[0])):
                arr[i][j] += r[1] if arr[i - 1][j] == r[0] else r[0]
        return min(arr[-1])

import heapq
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        def min_array_except_self(arr):
            res = arr[:]
            for i in range(len(res)):
                prev = arr[0:i]
                next = arr[i+1:] if i < len(arr)-1 else []
                res[i] = min(prev + next )

            return res
            
            
        l = len(arr)
        dp = [[0 for i in range(l)] for j in range(l)]
        res = inf
        
        for j in range(l):
            dp[0][j] = arr[0][j]
        
        mindp = dp[:]
        mindp[0] = min_array_except_self(dp[0])
        
        print(dp, \"||\", mindp)
        
        for i in range(1,l):
            for j in range(len(dp)):
                dp[i][j] = arr[i][j] + mindp[i-1][j]
                if i == l - 1:
                    res = min(res, dp[i][j])

            mindp[i] = min_array_except_self(dp[i])
            
        return res
                          
        
                           
                         
        
       
        
        
 # [1,2,3]
 # [4,5,6]
 # [7,8,9]

[[-2,-18,31,-10,-71,82,47,56,-14,42],
 [-95,3,65,-7,64,75,-51,97,-66,-28],
 [36,3,-62,38,15,51,-58,-90,-23,-63],
 [58,-26,-42,-66,21,99,-94,-95,-90,89],
 [83,-66,-42,-45,43,85,51,-86,65,-39],
 [56,9,9,95,-56,-77,-2,20,78,17],
 [78,-13,-55,55,-7,43,-98,-89,38,90],
 [32,44,-47,81,-1,-55,-5,16,-81,17],
 [-87,82,2,86,-88,-58,-91,-79,44,-9],
 [-96,-14,-52,-8,12,38,84,77,-51,52]]



class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(1, n:=len(arr)):
            for j in range(n):
                t = min(arr[i-1][0:j] + arr[i-1][j+1:n])
                arr[i][j] += t
                
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for row in range(1,len(arr)):
            for col in range(0, len(arr)):
                if col == 0:
                    arr[row][col] += min(arr[row-1][1:])
                elif col == len(arr)-1:
                    arr[row][col] += min(arr[row-1][:-1])
                else:
                    arr[row][col] += min(arr[row-1][:col] + arr[row-1][col+1:])
            
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = arr[0][:]

        for i, costs in enumerate(arr[1:], 1):
            prev = dp[:]
            
            for j, cost in enumerate(costs):
                dp[j] = cost + min(prev[:j] + prev[j+1:])

        return min(dp)
    
    
    
#         min_path_sum = float('inf')
        
#         def get_all_min_paths(arr, cur_row, cur_index, cur_sum):
#             nonlocal min_path_sum
#             if cur_row == len(arr):
#                 # print()
#                 min_path_sum = min(min_path_sum, cur_sum)
#             else: 
#                 current_row = arr[cur_row]
#                 for i in range(len(current_row)):
#                     if i != cur_index:
#                         ele = current_row[i]
#                         # print('cur_value', cur_index, 'ele', ele, 'cur_sum', cur_sum)
#                         get_all_min_paths(arr, cur_row+1, i, cur_sum+ele)
            
#             # pick one of the elements from the next row
#             # if its valye > cur 
#             # once reached len(arr) add path to array if its sum is 
#             # less than the current minimum 
            
        
        
#         get_all_min_paths(arr, 0, None, 0)
#         return min_path_sum 


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        A=arr
        n=len(A)
        for i in range(1,n):
            for j in range(n):
                res=A[i-1][0:j]+A[i-1][j+1:n]
                A[i][j]+=min(res)
        return min(A[n-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        nRow, nCol = len(arr), len(arr[0])
        # pathSum = [[0] * col for _ in range(row)] # row-by-col 2D array filled with 0
        pathSum = arr.copy()
        
        for row in range(-2, -nCol - 1, -1): # bottom-to-top
            for col in range(nCol): # left-to-right
                pathSum[row][col] += min(pathSum[row + 1][0:col] + pathSum[row + 1][col + 1:])
        
        return min(pathSum[0])


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(1,len(arr)):
            for j in range(len(arr[0])):
                arr[i][j]+=min(arr[i-1][:j]+arr[i-1][j+1:])
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m = len(arr)
        dp = [[0 for x in range(m)] for x in range(m)]
        
        for i in range(m):
            for j in range(m):
        
                if i == 0:
                    dp[i][j] = arr[i][j]
                   
                else:
                    temp = dp[i-1].copy()
                    temp.pop(j)
                    dp[i][j] = arr[i][j] + min(temp)
         
        return min(dp[m-1])
        


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        # [[1,2,3],
        #  [4,5,6],
        #  [7,8,9]]
        
        # do a dp where dp(i,j) returns the minimum path starting from (i,j)
        
        if not arr:
            return 0
        
        m = len(arr)
        n = len(arr[0])
        INF = float('inf')
        dp = [[INF]*n for _ in range(m)]
        
        dp[-1] = arr[-1]
        
        for i in range(m-2,-1,-1):
            for j in range(n):
                dp[i][j] = min(dp[i+1][:j]+dp[i+1][j+1:])+arr[i][j]
        print(dp)
        return min(dp[0])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [[-100 for _ in range(len(arr[0]))] for _ in range(len(arr))]
        mi, mis = 100, 100
        index = -1
        for j in range(len(arr[0])):
            dp[0][j] = arr[0][j]
            if dp[0][j] <= mi:
                mis = mi
                mi = dp[0][j]
                index = j
            elif dp[0][j] < mis:
                mia = dp[0][j]
        candidate = [mi, mis, index]
        #print(candidate)
        
        for i in range(1, len(arr)):
            nxt = [float(\"inf\"), float(\"inf\"), -1]
            for j in range(len(arr[0])):
                if j != candidate[2]:
                    dp[i][j] = candidate[0] + arr[i][j]
                    
                else:
                    dp[i][j] = candidate[1] + arr[i][j]
                
                if dp[i][j] <= nxt[0]:
                    nxt[1] = nxt[0]
                    nxt[0] = dp[i][j]
                    nxt[2] = j
                elif dp[i][j] < nxt[1]:
                    nxt[1] = dp[i][j]
            candidate = nxt[:]
            #print(candidate)
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        '''
        Time: O(mn)
        Space: O(n + n) ~ O(n)
        '''
        m = len(arr)
        n = len(arr[0])
        
        if m == 1: # 1 ele sq. matrix
            return arr[0][0]
        
        def get_min_neighbors(i, j):
            a, row_prev[j] = row_prev[j], float('inf')
            min_val = min(row_prev)
            row_prev[j] = a
            return min_val
        
        
        row_prev = arr[0]
        cur = [0]*n
        global_min = float('inf')
        
        for row in range(1, m):
            for col in range(n):
                cur[col] = get_min_neighbors(row, col) + arr[row][col]
                
                if row == m-1 and cur[col] < global_min:
                    global_min = cur[col]
     
            row_prev = cur[:]
            #print(cur)
        
        return global_min

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        for i in range(1, n):
            for j in range(n):
                prevmin = min(arr[i-1])
                temp = arr[i-1][:]
                temp.remove(prevmin)
                prevmin2 = min(temp)
                arr[i][j] += prevmin if prevmin != arr[i-1][j] else prevmin2 
        return min(arr[n-1])


class Solution:
    def minFallingPathSum(self, dp: List[List[int]]) -> int:
        for i in range(1, len(dp)):
            for j in range(len(dp[i])):
                dp[i][j] = min(dp[i-1][:j]+dp[i-1][j+1:]) + dp[i][j]

        return min(dp[-1])

from heapq import nsmallest
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        for i in range(m-1)[::-1]:
            for j in range(n):
                ans = nsmallest(2, arr[i+1])
                arr[i][j] += ans[0] if ans[0]!=arr[i+1][j] else ans[1]
        return min(arr[0])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        A = arr
        n = len(A)
        dp = [[float('inf') for _ in range(n)] for _ in range(n)]
        for c in range(n):
            dp[0][c] = A[0][c]
        
        for r in range(1, n):
            for c in range(n):
                prev = heapq.nsmallest(2, dp[r - 1])
                dp[r][c] = A[r][c]
                dp[r][c] += prev[1] if dp[r - 1][c] == prev[0] else prev[0]
        
        return min(dp[n - 1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr:
            return 0
        length=len(arr)
        for i in range(1,length):
            for j in range(length):
                if j==0:
                    arr[i][j]+=min(arr[i-1][j+1:])
                elif j==len(arr)-1:
                    arr[i][j]+=min(arr[i-1][:-1])
                else:
                    arr[i][j]+=min(arr[i-1][:j]+arr[i-1][j+1:])
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        dp = [[0] * n for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(n):
                m0, m1 = heapq.nsmallest(2, dp[i - 1])
                dp[i][j] = arr[i - 1][j] + (m0 if dp[i - 1][j] != m0 else m1)
                
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        for i in range(1, m):
            for j in range(n):
                m0, m1 = heapq.nsmallest(2, arr[i - 1])
                arr[i][j] += m0 if arr[i - 1][j] != m0 else m1
                
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        self.memo = {}
        if not arr:
            return 0
        
        possible_values = []
        for column in range(len(arr[0])):
            possible_values.append(self.visit_row(arr, 0, column))
            
        return min(possible_values)
        
        
    def visit_row(self, arr, i, j):
        if (i, j) in self.memo:
            return self.memo[(i,j)]
        # Base case
        if i == len(arr) - 1:
            return arr[i][j]
        val = arr[i][j]
        possible_values = []
        prev_val = 999999999999999
        for k in [i[0] for i in sorted(enumerate(arr[i+ 1]), key=lambda x:x[1])]:
            if k == j:
                continue
            next_val = self.visit_row(arr, i + 1, k)
            possible_values.append(next_val)
            if prev_val < next_val:
                break
            prev_val = next_val
        val += min(possible_values)
        self.memo[(i, j)] = val
        return val

# O(mn) time and O(1) space
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        
        for i in range(1, m):
            # find two smallest in prev row
            min1 = 0
            min2 = 1
            
            for j in range(1,n):
                if arr[i-1][j] < arr[i-1][min1]:
                    min2 = min1
                    min1 = j
                elif arr[i-1][j] < arr[i-1][min2]:
                    min2 = j
            
            # for j in range(n):
            #     if min1 == None or arr[i-1][min1]  > arr[i-1][j]:
            #         min2 = min1
            #         min1 = j
            #     elif min2 == None or arr[i-1][min2] > arr[i-1][j]:
            #         min2 = j
            
            for j in range(n):
                if j == min1:
                    arr[i][j] += arr[i-1][min2]
                else:
                    arr[i][j] += arr[i-1][min1]
        
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        min_path = float(\"inf\")
        n = len(arr)
        m = len(arr[0])
        for r in range(1, n):
            min_path = float(\"inf\")
            for c in range(0, m):
                arr[r][c] += sorted(arr[r-1][:c]+arr[r-1][c+1:])[0]
                min_path = min(min_path, arr[r][c])

        return min_path
                                
                                 
        
                                 

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        def second_smallest(nums):
            s1, s2 = float('inf'), float('inf')
            for num in nums:
                if num <= s1:
                    s1, s2 = num, s1
                elif num < s2:
                    s2 = num
            return s2
        
        n = len(arr)
        for i in range(1, n):
            for j in range(n):
                prevmin = min(arr[i-1])
                prevmin2 = second_smallest(arr[i-1])
                arr[i][j] += prevmin if prevmin != arr[i-1][j] else prevmin2 
        return min(arr[n-1])
    


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr:
            return 0
        rows, cols = len(arr), len(arr[0])
        
        for r in range(1, rows):
            for c in range(cols):
                val = float('inf')
                for x in range(cols):
                    if arr[r-1][x]<val and x!=c:
                        val = arr[r-1][x]
                arr[r][c] += val
        return min(arr[-1])


class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        cols = len(cost[0])
        dp = cost[0]

        for h in range(1, len(cost)):
            dp = [cost[h][m] + min(dp[prevMat]
                    for prevMat in range(0, cols)
                    if prevMat != m)
                 for m in range(0, cols)]

        return min(dp)

# O(mn) time and O(1) space
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        
        for i in range(1, m):
            min1, min2 = None, None
            
            for j in range(n):
                if min1 == None or arr[i-1][min1]  > arr[i-1][j]:
                    min2 = min1
                    min1 = j
                elif min2 == None or arr[i-1][min2] > arr[i-1][j]:
                    min2 = j
            
            for j in range(n):
                if j == min1:
                    arr[i][j] += arr[i-1][min2]
                else:
                    arr[i][j] += arr[i-1][min1]
        
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        pre = arr[0][:]
        for i in range(1, m):
            dp = []
            for j in range(n):
                dp += [arr[i][j] + min(pre[k] for k in range(n) if k != j)]
            pre = dp
        return min(dp)

class Solution:
    def minFallingPathSum(self, A):
        m, n = len(A), len(A[0])
        dp = A[0].copy()
        for x in range(1, m):
            tmp = [0] * n
            for y in range(n):
                tmp[y] = min(dp[py] for py in range(n) if y != py) + A[x][y]
            dp, tmp = tmp, dp
        return min(dp)  

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        
        temp_array = copy.deepcopy(arr[0])
        
        for i in range(1, len(arr)):
            print(temp_array)
            temp_array_new = [0]*len(arr)
            for j in range(0, len(arr)):
                mins = [temp_array[k] for k in range(len(arr)) if k != j]
                temp_array_new[j] = min(mins) + arr[i][j]
            temp_array = copy.deepcopy(temp_array_new)
            
        print(temp_array)
        
        return min(temp_array)


import numpy as np

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = arr[0]
        
        
        for r in range(1, len(arr)):
            new_dp = [i for i in dp]
            for c in range(len(arr)):
                lst = [dp[j] for j in range(len(arr)) if j != c]
                
                new_dp[c] = min(lst)+arr[r][c]
            dp = new_dp
        return int(min(dp))


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        while len(arr) > 1:
            bottom = arr.pop()
            for i in range(len(arr[-1])):
                arr[-1][i] += min(el for j, el in enumerate(bottom) if i != j)
            
        return min(arr[0])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        cumSum = [[0 for j in range(len(arr[0]) + 1)] for i in range(len(arr)+1)]
        for i in range(len(arr)):
            for j in range(len(arr[0])):
                cumSum[i+1][j+1] = arr[i][j] + cumSum[i+1][j] + cumSum[i][j+1] - cumSum[i][j]

        dp = [arr[i] for i in range(len(arr))]
        for i in range(1,len(dp)):
            for j in range(len(dp[0])):
                i1, j1 = i+1, j+1
                aboveDP = min([x for c,x in enumerate(dp[i-1]) if c != j])
                dp[i][j] = cumSum[i1][j1] - cumSum[i][j1] - cumSum[i1][j] + cumSum[i][j] + aboveDP

        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr or not arr[0]:
            raise ValueError(\"empty input.\")
        
        m = len(arr) # row
        n = len(arr[0]) # col
        dp = list(arr[0]) # start with first row.
        
        for row in arr[1:]:
            dp_new = [0] * n
            for i in range(n):
                dp_new[i] = row[i] + min([x for i_prev, x in enumerate(dp) if i != i_prev])
            dp = dp_new
            
        return min(dp_new)

class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        
        numHouses = len(cost)
        cols = len(cost[0])
        dp = cost[0]

        for h in range(1, numHouses):
            newRow = [0 for _ in range(cols)]
            for m in range(0, cols):
                prevCost = min(dp[prevMat]
                    for prevMat in range(0, cols)
                    if prevMat != m)
                newRow[m] = (cost[h][m] + prevCost)
            dp = newRow

        return min(dp)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        cumSum = [[0 for j in range(len(arr[0]) + 1)] for i in range(len(arr)+1)]
        for i in range(len(arr)):
            for j in range(len(arr[0])):
                cumSum[i+1][j+1] = arr[i][j] + cumSum[i+1][j] + cumSum[i][j+1] - cumSum[i][j]

        dp = [arr[i] for i in range(len(arr))]
        for i in range(1,len(dp)):
            for j in range(len(dp[0])):
                csR, csC = i+1, j+1
                leftR, leftC = i, j+1
                topR, topC = i+1, j
                addR, addC = i, j
                aboveDP = min([x for c,x in enumerate(dp[i-1]) if c != j])
                dp[i][j] = cumSum[csR][csC] - cumSum[leftR][leftC] - cumSum[topR][topC] + cumSum[addR][addC] + aboveDP

        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m=len(arr)
        print(m)
        if m==1:
            return min(arr[0])
        dp=[[0 for x in range(m)]for x in range(m)]
        for i in range(m):
            for j in range(m):
                if i==0:
                    dp[i][j]=arr[i][j]
                else:
                    minn=1000
                    for k in range(0,m):
                        if k!=j and dp[i-1][k]<minn:
                            minn=dp[i-1][k]
                    dp[i][j]=minn+arr[i][j]
        print(dp)
        return min(dp[m-1])

import heapq
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        while len(arr) > 1:
            row = arr.pop()
            heap = []
        
            for i in range(len(row)):
                if not heap:
                    heap = [row[x] for x in range(len(row)) if x != i]
                    heapq.heapify(heap)
                
                else:
                    if heap[0] == row[i]:
                        heapq.heappop(heap)
                    heapq.heappush(heap, row[i-1])
                    
                arr[-1][i] += heap[0]
        
        return min(arr[0])



class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        R,C = len(arr), len(arr[0])
        
        DP = [[float(\"inf\")]*C for i in range(R)]
        
        #fill the 1st row with same values:
        for j in range(C):
            DP[0][j]=arr[0][j]
        
        for i in range(1,R):
            for j in range(C):
                #if left edge--> then nothing on left
                if(j==0):
                    DP[i][j] = min(arr[i][j]+DP[i-1][k] for k in range(j+1,C))
                
                #if right edge--> then nothing on right
                elif(j==C-1):
                    DP[i][j] = min(arr[i][j]+DP[i-1][k] for k in range(j-1,-1,-1))
                    
                #else--> both from left & right
                else:
                    left = min(DP[i-1][k] for k in range(0,j))
                    right = min(DP[i-1][k] for k in range(j+1,C))
                    DP[i][j] = min(left+arr[i][j],right+arr[i][j])
        
        return min(DP[R-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        R,C = len(arr), len(arr[0])
        
        DP = [[float(\"inf\")]*C for i in range(R)]
        
        #fill the 1st row with same values:
        for j in range(C):
            DP[0][j]=arr[0][j]
        
        for i in range(1,R):
            for j in range(C):
                #if left edge--> then nothing on left
                if(j==0):
                    DP[i][j] = min(arr[i][j]+DP[i-1][k] for k in range(j+1,C))
                
                #if right edge--> then nothing on right
                elif(j==C-1):
                    DP[i][j] = min(arr[i][j]+DP[i-1][k] for k in range(j-1,-1,-1))
                    
                #else--> both from left & right
                else:
                    left = min(DP[i-1][k] for k in range(0,j))
                    right = min(DP[i-1][k] for k in range(j+1,C))
                    DP[i][j] = min(left+arr[i][j],right+arr[i][j])
        
        return min(DP[R-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        R,C = len(arr), len(arr[0])
        
        DP = [[float(\"inf\")]*C for i in range(R)]
        
        #fill the 1st row with same values:
        for j in range(C):
            DP[0][j]=arr[0][j]
        
        for i in range(1,R):
            for j in range(C):
                #if left edge--> then nothing on left
                if(j==0):
                    DP[i][j] = min(arr[i][j]+DP[i-1][k] for k in range(j+1,C))
                
                #if right edge--> then nothing on right
                elif(j==C-1):
                    DP[i][j] = min(arr[i][j]+DP[i-1][k] for k in range(j-1,-1,-1))
                    
                #else--> both from left & right
                else:
                    left = min(DP[i-1][k] for k in range(0,j))
                    right = min(DP[i-1][k] for k in range(j+1,C))
                    DP[i][j] = min(left+arr[i][j],right+arr[i][j])
        
        return min(DP[R-1])
        
        

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        R,C = len(arr), len(arr[0])
        
        DP = [[float(\"inf\")]*C for i in range(R)]
        
        #fill the 1st row with same values:
        for j in range(C):
            DP[0][j]=arr[0][j]
        
        for i in range(1,R):
            for j in range(C):
                #if left edge--> then nothing on left
                if(j==0):
                    DP[i][j] = min(arr[i][j]+DP[i-1][k] for k in range(j+1,C))
                
                #if right edge--> then nothing on right
                elif(j==C-1):
                    DP[i][j] = min(arr[i][j]+DP[i-1][k] for k in range(j-1,-1,-1))
                    
                #else--> both from left & right
                else:
                    left = min(DP[i-1][k] for k in range(0,j))
                    right = min(DP[i-1][k] for k in range(j+1,C))
                    DP[i][j] = min(left+arr[i][j],right+arr[i][j])
        
        return min(DP[R-1])
        

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        
        for i in range(1, len(arr)):
            for j in range(len(arr[0])):
                
                curr_min = float(\"inf\")
                #need a for loop to try all directions.
                for k in range(len(arr[0])):                    
                    if k == j:
                        continue
                                        
                    if arr[i - 1][k] < curr_min:
                        curr_min = arr[i - 1][k]
                
                arr[i][j] += curr_min
                
                
        return min(arr[-1])

    

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(len(arr)-2, -1, -1):
            a = sorted([arr[i+1][j], j] for j in range(len(arr[0])))
            for j in range(len(arr[0])):
                for v, idx in a:
                    if idx != j:
                        arr[i][j] += v
                        break
        return min(arr[0])

class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        
        numHouses = len(cost)
        cols = len(cost[0])
        dp = cost[0]

        for h in range(1, numHouses):
            newRow = [0 for _ in range(cols)]
            for m in range(0, cols):
                prevCost = min([dp[prevMat]
                    for prevMat in range(0, cols)
                    if prevMat != m])
                newRow[m] = (cost[h][m] + prevCost)
            dp = newRow

        return min(dp)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp_mtx = [[0] * len(arr[0]) for _ in range(len(arr))]
        
        for i in range(len(arr)):
            for j in range(len(arr[0])):
                if i == 0:
                    dp_mtx[i][j] = arr[i][j]
                else:
                    dp_mtx[i][j] = arr[i][j] + min(dp_mtx[i - 1][k] for k in range(len(arr[0])) if k != j)
        
        return min(dp_mtx[len(arr) - 1])


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        for i in range(1, n): # for each row after the first
            for j in range(n): # for each col
                # collect the non-adjacent cols in the prev row
                prevNonAdj = [arr[i-1][k] for k in range(n) if k != j]
                # add the min of the prev non-adj cols to the curr col
                # since modifying arr directly, sum accumulates
                arr[i][j] += min(prevNonAdj)
        return min(arr[n-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp_mtx = [[0] * len(arr[0]) for _ in range(len(arr))]
        
        for i in range(len(arr)):
            for j in range(len(arr[0])):
                if i == 0:
                    dp_mtx[i][j] = arr[i][j]
                else:
                    dp_mtx[i][j] = arr[i][j] + min(dp_mtx[i - 1][k] for k in range(len(arr[0])) if k != j)
                                
        for i in range(len(dp_mtx)):
            print(dp_mtx[i])
        
        return min(dp_mtx[len(arr) - 1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [[float('inf')] + i + [float('inf')] for i in arr]
        for i in range(1,len(dp)):
            for j in range(1,len(dp[0])-1):
                dp[i][j] = dp[i][j] + min([dp[i-1][k] for k in range(len(dp[i-1])) if k != j])
                
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        for i in range(m-1)[::-1]:
            for j in range(n):
                arr[i][j] += min(arr[i+1][k] for k in range(n) if k != j)
        return min(arr[0])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        dp1 = [None for i in range(n)]
        for i in range(0,n):
            dp1[i] = arr[0][i]
        for i in range(1,n):
            dp2 = [None for i in range(n)]
            for j in range(0,n):
                minList = []
                for k in range(0,n):
                    if k == j:
                        continue
                    minList.append(dp1[k])
                dp2[j] = min(minList)+arr[i][j]
            dp1 = dp2
        return min(dp2)


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m = len(arr)
        n = len(arr[0])
        
        for i in range(1, m):
            for j in range(0, n):
                arr[i][j] += min([arr[i-1][k] for k in range(0, n) if k != j])
        return min(arr[-1])


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        m, n = len(arr), len(arr[0])
        
        dp = [[float('inf')] * n for _ in range(m)]
        
        
        
        for i in range(m):
            for j in range(n):
                if i == 0:
                    dp[0][j] = arr[0][j]
                else:
                    dp[i][j] = arr[i][j] + min(dp[i-1][x] for x in range(n) if x != j)
                    
        return min(dp[-1])
                


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr:
            return 0
        m, n = len(arr), len(arr[0])
        for i in range(1, m):
            for j in range(n):
                arr[i][j] = min([arr[i-1][col] for col in range(n) if col != j])+arr[i][j]
        
        return min(arr[-1])


class Solution(object):
    def minFallingPathSum(self, a):
        \"\"\"
        :type arr: List[List[int]]
        :rtype: int
        \"\"\"
        n=len(a)
        if(n==1):
            return a[0][0]
        dp=[[0 for i in range(n)]for j in range(n)]
        pos1=-1
        pos2=-1
        for i in range(n):
            print(pos1,pos2)
            for j in range(n):
                dp[i][j]=a[i][j]
                if i==0:
                    continue
                if j==pos1:
                    dp[i][j]+=dp[i-1][pos2]
                else:
                    dp[i][j]+=dp[i-1][pos1]
            pos1=0
            pos2=1
            if dp[i][0]>dp[i][1]:
                pos1,pos2=pos2,pos1
            for j in range(2,n):
                if dp[i][j]<dp[i][pos1]:
                    pos2=pos1
                    pos1=j
                elif dp[i][j]<dp[i][pos2]:
                    pos2=j
        print(dp)      
        return dp[-1][pos1]

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        dp = [[float('inf')] * n for _ in range(m)]
        dp[0] = arr[0]
        for i in range(1, m):
            for j in range(n):
                dp[i][j] = min([dp[i-1][k] for k in range(n) if k != j]) + arr[i][j]
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = arr[:]
        m, n = len(arr), len(arr[0])
        for i in range(1, m):
            for j in range(n):
                dp[i][j] = arr[i][j] + min(dp[i - 1][k] for k in range(n) if k != j)
        return min(dp[-1])

import heapq
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
       
        l = len(arr)
        dp = [[0 for i in range(l)] for j in range(l)]
        res = inf
    
        for j in range(l):
            dp[0][j] = arr[0][j]
        
        print(dp)
        
        for i in range(1,l):
            for j in range(len(dp)):
                minr = min([dp[i-1][k] for k in range(l) if k != j])
                dp[i][j] = arr[i][j] + minr
                if i == l - 1:
                    res = min(res, dp[i][j])
        
        return res
                          
        
                           
                         
        
       
        
        
 # [1,2,3]
 # [4,5,6]
 # [7,8,9]

[[-2,-18,31,-10,-71,82,47,56,-14,42],
 [-95,3,65,-7,64,75,-51,97,-66,-28],
 [36,3,-62,38,15,51,-58,-90,-23,-63],
 [58,-26,-42,-66,21,99,-94,-95,-90,89],
 [83,-66,-42,-45,43,85,51,-86,65,-39],
 [56,9,9,95,-56,-77,-2,20,78,17],
 [78,-13,-55,55,-7,43,-98,-89,38,90],
 [32,44,-47,81,-1,-55,-5,16,-81,17],
 [-87,82,2,86,-88,-58,-91,-79,44,-9],
 [-96,-14,-52,-8,12,38,84,77,-51,52]]



class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m = len(arr)
        n = len(arr[0])
        dp = [[0]*n for i in range(m)]

        for j in range(n):
            dp[0][j] = arr[0][j]

        for i in range(1,m):
            for j in range(n):
                dp[i][j] = min([dp[i-1][k] for k in range(n) if k!=j]) + arr[i][j]

        return min(dp[m-1])


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        R = len(arr)
        C = len(arr[0])
        
        dp = [[float('inf') for j in range(C)] for i in range(R)]
        
        for i in range(C):
            dp[0][i] = arr[0][i]
            
        for r in range(1,R):
            for c in range(C):
                dp[r][c] = arr[r][c] + min(dp[r-1][k] if k!=c else float('inf') for k in range(C))
                
        return min(dp[R-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr:
            return 0
        m, n = len(arr), len(arr[0])
        dp = [[float('inf')]*n for _ in range(m)]
        dp[0] = arr[0]
        for i in range(1, m):
            for j in range(n):
                dp[i][j] = min([dp[i-1][col] for col in range(n) if col != j])+arr[i][j]
        
        return min(dp[-1])

class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        cols = len(cost[0])
        dp = cost[0]

        for h in range(1, len(cost)):
            for m in range(0, cols):
                cost[h][m] += min(cost[h-1][prevMat]
                        for prevMat in range(0, cols)
                        if prevMat != m)
                 

        return min(cost[-1])

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        for i in range(len(A)-1):
            x = [0 for _ in A]
            for j in range(len(A)):
                ls = []
                for k in range(len(A)):
                    if not j==k:
                        ls.append(A[0][k])
                        
                x[j] = A[i+1][j]+min(ls)
                
            A[0] = x
                
        return min(A[0])

class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        
        numHouses = len(cost)
        numMaterials = len(cost[0])
        dp = cost[0]

        for h in range(1, numHouses):
            newRow = [0 for _ in range(numMaterials)]
            for m in range(1, numMaterials+1):
                prevCost = min([dp[prevMat-1]
                    for prevMat in range(1, numMaterials+1)
                    if prevMat != m])
                newRow[m-1] = (cost[h][m-1] + prevCost)
            dp = newRow

        return min(dp)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        memo = {}
        return self.helper(0,None,arr,memo)
        
    def helper(self,index,notAllowed,arr,memo):
        if (index == len(arr)):
            return 0
        elif (index,notAllowed) in memo:
            return memo[(index,notAllowed)]
        else:
            maxOne,maxTwo = self.getMaxTwo(notAllowed,arr[index])
            useOne = arr[index][maxOne] + self.helper(index + 1,maxOne,arr,memo)
            useTwo = arr[index][maxTwo] + self.helper(index + 1,maxTwo,arr,memo)
            res = min(useOne,useTwo)
            memo[(index,notAllowed)] = res
            return res
                
    def getMaxTwo(self,blocked,arr):
        minOne = None
        minIndex = None
        for i in range (len(arr)):
            if (i == blocked):
                continue
            else:
                curr_num = arr[i]
                if (minOne == None) or (curr_num < minOne):
                    minOne = curr_num
                    minIndex = i
        minTwo = None
        minIndexTwo = None
        for j in range (len(arr)):
            if (j == blocked) or (j == minIndex):
                continue
            else:
                curr_num = arr[j]
                if (minTwo == None) or (curr_num < minTwo):
                    minTwo = curr_num
                    minIndexTwo = j
        return minIndex,minIndexTwo
        


class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        
        numHouses = len(cost)
        cols = len(cost[0])
        dp = cost[0]

        for h in range(1, numHouses):
            newRow = [0 for _ in range(cols)]
            for m in range(0, cols):
                newRow[m] = cost[h][m] + min(dp[prevMat]
                    for prevMat in range(0, cols)
                    if prevMat != m)
            dp = newRow

        return min(dp)

class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        
        numHouses = len(cost)
        numMaterials = len(cost[0])
        dp = cost[0]

        for h in range(1, numHouses):
            newRow = []
            for m in range(1, numMaterials+1):
                prevCost = min([dp[prevMat-1]
                    for prevMat in range(1, numMaterials+1)
                    if prevMat != m])
                newRow.append(cost[h][m-1] + prevCost)
            dp = newRow

        return min(dp)

class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        dp = [cost[0]]
        numHouses = len(cost)
        numMaterials = len(cost[0])

        for h in range(1, numHouses):
            newRow = []
            for m in range(1, numMaterials+1):
                prevCost = min([dp[-1][prevMat-1]
                    for prevMat in range(1, numMaterials+1)
                    if prevMat != m])
                newRow.append(cost[h][m-1] + prevCost)
            dp.append(newRow)

        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(1,len(arr)):
            for j in range(len(arr[0])):
                above = set()
                for k in range(len(arr[0])):
                    if k!=j:
                        above.add(arr[i-1][k])
                #print(above)
                arr[i][j] = arr[i][j] + min(above)
        
        #for row in arr:
            #print(row)
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, A):
        m, n = len(A), len(A[0])
        dp = A[0].copy()
        for x in range(1, m):
            tmp = [0] * n
            for y in range(n):
                tmp[y] = min(dp[py] + A[x][y] for py in range(n) if y != py )
            dp, tmp = tmp, dp
        return min(dp)  

class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        
        numHouses = len(cost)
        cols = len(cost[0])
        dp = cost[0]

        for h in range(1, numHouses):
            newRow = [0 for _ in range(cols)]
            for m in range(1, cols+1):
                prevCost = min([dp[prevMat-1]
                    for prevMat in range(1, cols+1)
                    if prevMat != m])
                newRow[m-1] = (cost[h][m-1] + prevCost)
            dp = newRow

        return min(dp)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [arr[i] for i in range(len(arr))]
    
        for i in range(1,len(arr)):
            for j in range(len(arr[0])):
                opts = [ (arr[i][j]+x) for c,x in enumerate(arr[i-1]) if c != j]
                dp[i][j] = min(opts)
        return min(dp[-1])

import heapq
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        def min_array_except_self(arr):
            res = arr[:]
            for i in range(len(res)):
                prev = arr[0:i]
                next = arr[i+1:] if i < len(arr)-1 else []
                res[i] = min(prev + next )

            return res
            
            
        l = len(arr)
        dp = [[0 for i in range(l)] for j in range(l)]
        res = inf
        
        for j in range(l):
            dp[0][j] = arr[0][j]
        
        mindp = dp[:]
        mindp[0] = min_array_except_self(dp[0])
        
        print(dp, \"||\", mindp)
        
        for i in range(1,l):
            for j in range(len(dp)):
                minr = min([dp[i-1][k] for k in range(l) if k != j])
                dp[i][j] = arr[i][j] + minr
                if i == l - 1:
                    res = min(res, dp[i][j])

            mindp[i] = min_array_except_self(dp[i])
            
        return res
                          
        
                           
                         
        
       
        
        
 # [1,2,3]
 # [4,5,6]
 # [7,8,9]

[[-2,-18,31,-10,-71,82,47,56,-14,42],
 [-95,3,65,-7,64,75,-51,97,-66,-28],
 [36,3,-62,38,15,51,-58,-90,-23,-63],
 [58,-26,-42,-66,21,99,-94,-95,-90,89],
 [83,-66,-42,-45,43,85,51,-86,65,-39],
 [56,9,9,95,-56,-77,-2,20,78,17],
 [78,-13,-55,55,-7,43,-98,-89,38,90],
 [32,44,-47,81,-1,-55,-5,16,-81,17],
 [-87,82,2,86,-88,-58,-91,-79,44,-9],
 [-96,-14,-52,-8,12,38,84,77,-51,52]]



class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        costs = [[None for i in range(len(A))] for j in range(len(A[0]))]
        
        for j in range(len(A)):
            costs[0] = A[0]
        
        for i in range(1, len(A)):
            for j in range(len(A)):
                parents = list()
                for p in range(len(A)):
                    if p != j:
                        parents.append(costs[i-1][p])
                
                costs[i][j] = min(parents) + A[i][j]
        
        return min(costs[len(A)-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        T = [[0 for _ in range(len(arr))] for _ in range(len(arr))]
        T[0] = arr[0]
        for i in range(1, len(arr)):
            for j in range(len(arr)):
                T[i][j] = arr[i][j] + min([T[i-1][c] for c in range(len(arr)) if c != j])
        return min(T[-1])

import heapq as pq
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        rows = len(arr)
        cols = len(arr[0])
        
        # Find first min, the 2nd min
        min_vals = []
        for i in range(cols):
            pq.heappush(min_vals, (arr[0][i], i))

        min_vals = pq.nsmallest(2, min_vals)
        
        for i in range(1, cols):
            # print(min_vals)
            
            new_min_vals = []
            (min_val2, _) = min_vals.pop()
            (min_val, min_col) = min_vals.pop()
            for col in range(cols):
                arr[i][col] += min_val if min_col != col else min_val2
                pq.heappush(new_min_vals, (arr[i][col], col))
            min_vals = pq.nsmallest(2, new_min_vals)
            # print(i, arr)
        return min(arr[-1])

\"\"\"


dp[r][c] = the minimum sum of falling int to row r and column c

dp[r][c] = arr[r][c] + min(dp[r-1][pc] for all pc != c)

\"\"\"



class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        rows = len(arr)
        cols = len(arr[0])
        infi = float('inf')
        dp = [[infi]*cols for _ in range(rows)]
        for c in range(cols):
            dp[0][c] = arr[0][c]
            
        for r in range(1, rows):
            for c in range(cols):
                dp[r][c] = arr[r][c] + min(dp[r-1][pc] for pc in range(cols) if pc != c)
        return min(dp[-1])    
                    

\"\"\"


dp[r][c] = the minimum sum of falling int to row r and column c

dp[r][c] = arr[r][c] + min(dp[r-1][pc] for all pc != c)

\"\"\"



class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        rows = len(arr)
        cols = len(arr[0])
        infi = float('inf')
        dp = [[infi]*cols for _ in range(rows)]
        for c in range(cols):
            dp[0][c] = arr[0][c]
            
        for r in range(1, rows):
            for c in range(cols):
                dp[r][c] = arr[r][c] + min(dp[r-1][pc] for pc in range(cols) if pc != c)
        print(dp)                
        return min(dp[-1])    
                    

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [[0] * len(arr[0]) for _ in arr]
        
        for i in range(len(arr)):
            if i == 0:
                dp[i] = arr[i]
            else:
                for j in range(len(arr[0])):
                    dp[i][j] = self.min_exclude(dp[i - 1], j) + arr[i][j]
                    
        return min(dp[-1])
                  
                
    def min_exclude(self, array, exclude):
        if len(array) == 0:
            return None
        out = float('inf')
        for i in range(len(array)):
            if i != exclude:
                out = min(out, array[i])
        return out


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        A = arr
        for i in range(1, len(A)):
            for j in range(len(A[0])):
                if j==0:
                    A[i][j] += min([A[i-1][j] for j in range(1, len(A))])
                elif j == len(A[0])-1:
                    A[i][j] += min([A[i-1][j] for j in range(0, len(A)-1)])
                else:
                    A[i][j] += min([A[i-1][j] for j in [x for x in range(len(A)) if x !=j]])
            
        return min(A[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        m=len(arr)
        
        for i in range(1,m):
            for j in range(m):
                res=float('inf')
                for x in range(m):
                    if x!=j:
                        if arr[i][j]+arr[i-1][x]<res:
                            res=arr[i][j]+arr[i-1][x]
                arr[i][j]=res
                    
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        dp = [[None for i in range(n)] for i in range(n)]
        for i in range(0,n):
            dp[0][i] = arr[0][i]
        for i in range(1,n):
            for j in range(0,n):
                minList = []
                for k in range(0,n):
                    if k == j:
                        continue
                    minList.append(dp[i-1][k])
                dp[i][j] = min(minList)+arr[i][j]
        return min(dp[n-1])


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        # brute force recursive solution (TLE)
        # answer = float(\"inf\")
        # def helper(rowIdx, prevIdx, curr): 
        #     nonlocal answer
        #     if rowIdx == len(arr):
        #         answer = min(answer, sum(curr))
        #         return
        #     row = arr[rowIdx]
        #     for i in range(len(row)):
        #         if rowIdx != 0 and i != prevIdx:
        #             curr.append(row[i])
        #             helper(rowIdx+1, i, curr)
        #             curr.pop()
        #         elif rowIdx == 0: 
        #             curr.append(row[i])
        #             helper(rowIdx+1, i, curr)
        #             curr.pop()        
        # helper(0, 0, [])
        # return answer
        
        # bottom-up DP solution
        dp = [[0 for _ in range(len(arr))] for _ in range(len(arr[0]))]
        for i in range(len(dp)):
            dp[0][i] = arr[0][i]
        
        for i in range(1, len(dp)):
            for j in range(len(dp[i])):
                if j == 0: # left edge
                    dp[i][j] = min(arr[i][j] + dp[i-1][k] for k in range(1, len(dp[i])))
                elif j == len(dp[i])-1: # right edge
                    dp[i][j] = min(arr[i][j] + dp[i-1][k] for k in range(len(dp[i])-1))
                else: # in between 
                    left_max = min(arr[i][j] + dp[i-1][k] for k in range(j))
                    right_max = min(arr[i][j] + dp[i-1][k] for k in range(j+1, len(dp[i])))
                    dp[i][j] = min(left_max, right_max)
    
        return min(dp[-1])


        
                
                
                
                
        


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        m=len(arr)
        
        for i in range(1,m):
            for j in range(m):
                res=float('inf')
                for x in range(m):
                    val=arr[i][j]+arr[i-1][x]
                    if x!=j and val<res:
                        res=val
                arr[i][j]=res
                    
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        \"\"\"
        for each column, we can either choose or not choose
        if we choose one, then the adjacent rows cannot choose the same column
                                    []
                             1       2       3 
                        
                          5   6    4   6    4   5
                       
                       7   9 7  8 
        \"\"\"
        # brute force recursive solution
        # answer = float(\"inf\")
        # def helper(rowIdx, prevIdx, curr): 
        #     nonlocal answer
        #     if rowIdx == len(arr):
        #         answer = min(answer, sum(curr))
        #         return
        #     row = arr[rowIdx]
        #     for i in range(len(row)):
        #         if rowIdx != 0 and i != prevIdx:
        #             curr.append(row[i])
        #             helper(rowIdx+1, i, curr)
        #             curr.pop()
        #         elif rowIdx == 0: 
        #             curr.append(row[i])
        #             helper(rowIdx+1, i, curr)
        #             curr.pop()        
        # helper(0, 0, [])
        # return answer
        
        dp = [[0 for _ in range(len(arr))] for _ in range(len(arr[0]))]
        for i in range(len(dp)):
            dp[0][i] = arr[0][i]
        
        for i in range(1, len(dp)):
            for j in range(len(dp[i])):
                if j == 0: # left edge
                    dp[i][j] = min(arr[i][j] + dp[i-1][k] for k in range(1, len(dp[i])))
                elif j == len(dp[i])-1: # right edge
                    dp[i][j] = min(arr[i][j] + dp[i-1][k] for k in range(len(dp[i])-1))
                else: # in between 
                    left_max = min(arr[i][j] + dp[i-1][k] for k in range(j))
                    right_max = min(arr[i][j] + dp[i-1][k] for k in range(j+1, len(dp[i])))
                    dp[i][j] = min(left_max, right_max)
    
        return min(dp[-1])


        
                
                
                
                
        
        

from heapq import nsmallest
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [[0] * len(arr[0]) for _ in range(len(arr))]
        dp[0] = arr[0]
        for i in range(1, len(arr)):
            min1, min2 = nsmallest(2, arr[i - 1])
            for j in range(len(arr[0])):
                if arr[i - 1][j] == min1:
                    arr[i][j] += min2
                else:
                    arr[i][j] += min1
        return min(arr[-1])
                


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        # brute force recursive solution
        # answer = float(\"inf\")
        # def helper(rowIdx, prevIdx, curr): 
        #     nonlocal answer
        #     if rowIdx == len(arr):
        #         answer = min(answer, sum(curr))
        #         return
        #     row = arr[rowIdx]
        #     for i in range(len(row)):
        #         if rowIdx != 0 and i != prevIdx:
        #             curr.append(row[i])
        #             helper(rowIdx+1, i, curr)
        #             curr.pop()
        #         elif rowIdx == 0: 
        #             curr.append(row[i])
        #             helper(rowIdx+1, i, curr)
        #             curr.pop()        
        # helper(0, 0, [])
        # return answer
        
        # bottom-up DP solution
        dp = [[0 for _ in range(len(arr))] for _ in range(len(arr[0]))]
        for i in range(len(dp)):
            dp[0][i] = arr[0][i]
        
        for i in range(1, len(dp)):
            for j in range(len(dp[i])):
                if j == 0: # left edge
                    dp[i][j] = min(arr[i][j] + dp[i-1][k] for k in range(1, len(dp[i])))
                elif j == len(dp[i])-1: # right edge
                    dp[i][j] = min(arr[i][j] + dp[i-1][k] for k in range(len(dp[i])-1))
                else: # in between 
                    left_max = min(arr[i][j] + dp[i-1][k] for k in range(j))
                    right_max = min(arr[i][j] + dp[i-1][k] for k in range(j+1, len(dp[i])))
                    dp[i][j] = min(left_max, right_max)
    
        return min(dp[-1])


        
                
                
                
                
        


from functools import lru_cache

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr:
            return 0
        
        cols = set(range(len(arr[0])))
        
        @lru_cache(maxsize=None)
        def path_sum(row, col):
            ret = arr[row][col]
            if row == len(arr) - 1:
                return ret
            
            other_cols = cols - {col}
            ret += min(path_sum(row+1,_) for _ in other_cols)
            return ret
        
        return min(path_sum(0, _) for _ in cols)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [[0 for _ in range(len(arr[0]))] for _ in range(len(arr))]
        for i in range(len(dp[0])):
            dp[0][i] = arr[0][i]
            
        for i in range(1, len(dp)):
            for j in range(len(dp[0])):
                mi = -1
                for k in range(len(dp[0])):
                    if not j == k:
                        if mi == -1 or dp[i-1][k] + arr[i][j] < mi:
                            mi = dp[i-1][k] + arr[i][j]
                dp[i][j] = mi
        
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [[0] * len(arr[0]) for _ in range(len(arr))]
        dp[0] = arr[0][:]
        for i in range(1, len(arr)):
            for j in range(len(arr[0])):
                dp[i][j] = min([arr[i][j] + dp[i-1][k] for k in range(len(arr[0])) if k != j])
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        @functools.lru_cache(None)
        def dp(i, j):
            if i == 0: 
                return arr[0][j]
            if i == len(arr): 
                return min(dp(i-1, k) for k in range(len(arr[0])))
            return arr[i][j] + min(dp(i-1, k) for k in range(len(arr[0])) if k!=j)
        return dp(len(arr), -1)  

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        @functools.lru_cache(None)
        def dp(i, j):
            if i == 0: return arr[0][j]
            return arr[i][j] + min(dp(i-1, k) for k in range(len(arr[0])) if k!=j)
        return min(dp(len(arr)-1, i) for i in range(len(arr[0])))

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        total = 0
        for row in range(len(arr)-1):
            row1_min, row2_min = min(arr[row]), min(arr[row+1])
            i1, i2 = arr[row].index(row1_min), arr[row+1].index(row2_min)
            if i1 != i2:
                total += row1_min
            else:
                total = False
                break
        if total:
            return total + min(arr[-1])
        dp = [[arr[j][i] if j == 0 else float('inf') for i in range(len(arr))] for j in range(len(arr))]
        for row in range(len(arr)-1):
            for col in range(len(arr[row])):
                for next_col in range(len(arr[row])):
                    if next_col != col:
                        dp[row+1][next_col] = min(dp[row+1][next_col], dp[row][col] + arr[row+1][next_col])
        return min(dp[len(arr)-1])

from typing import List
from functools import lru_cache

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        
        @lru_cache(None)
        def helper(r, c):
            if r == m:
                return 0
            return arr[r][c] + min(helper(r + 1, nc) for nc in range(n) if nc != c)
        
        return min(helper(0, c) for c in range(n))

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        if n == 1:
            return arr[0][0]
        firstRow = arr[0]
        srow = sorted([(num, idx) for idx, num in enumerate(firstRow)])
        cand1, cand2 = srow[0], srow[1]
        for row in arr[1:]:
            srow = sorted([(num, idx) for idx, num in enumerate(row)])
            # minimum, second minimum
            num1, idx1 = srow[0][0], srow[0][1]
            num2, idx2 = srow[1][0], srow[1][1]
            c1v = min(float('inf') if cand1[1] == idx1 else cand1[0] + num1, \\
                      float('inf') if cand2[1] == idx1 else cand2[0] + num1)
            c2v = min(float('inf') if cand1[1] == idx2 else cand1[0] + num2, \\
                      float('inf') if cand2[1] == idx2 else cand2[0] + num2)
            cand1 = (c1v, idx1)
            cand2 = (c2v, idx2)
        return min(cand1[0], cand2[0])
            
            
            

import heapq, bisect
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr or not arr[0]:
            raise ValueError(\"empty input.\")
        
        m = len(arr) # row
        n = len(arr[0]) # col
        dp = [0] * n
        prev_min = [(0, -1), (0, -1)]

        for row in arr:
            dp_new = [0] * n
            curr_min = []
            for i, num in enumerate(row):
                if i == prev_min[0][1]:
                    dp_new[i] = prev_min[1][0] + num
                else:
                    dp_new[i] = prev_min[0][0] + num
                bisect.insort(curr_min, (dp_new[i], i))
                
                if len(curr_min) > 2:
                    curr_min.pop()
            prev_min = curr_min
            dp = dp_new
        return min(dp)
        # dp = [(x, i) for i, x in enumerate(arr[0])] # start with first row.
        # heapq.heapify(dp)
        # # O(mnlogn) solution
        # for row in arr[1:]:
        #     dp_new = []
        #     for i in range(n):
        #         if dp[0][1] == i:
        #             tmp = heapq.heappop(dp)
        #             heapq.heappush(dp_new, (dp[0][0] + row[i], i))
        #             heapq.heappush(dp, tmp)
        #         else:
        #             heapq.heappush(dp_new, (dp[0][0] + row[i], i))
        #     dp = dp_new
        # return dp[0][0]
#         # O(mn^2) solution:
#         for row in arr[1:]:
#             dp_new = [0] * n
#             for i in range(n):
#                 dp_new[i] = row[i] + min([x for i_prev, x in enumerate(dp) if i != i_prev])
#             dp = dp_new
            
#         return min(dp_new)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n=len(arr)
        m=len(arr[0])
        dp=[[sys.maxsize]*m for i in range(n)]
        for j in range(m):
            dp[0][j]=arr[0][j]
        for i in range(1,n):
            for j in range(m):
                val=sys.maxsize
                for k in range(m):
                    if k !=j:
                        val=min(val,dp[i-1][k])
                dp[i][j]=val+arr[i][j]
        return min(dp[-1][:])

from functools import lru_cache
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        @lru_cache(maxsize=None)
        def dp(i,j):
            if not (0<=i<len(arr) and 0<=j<len(arr[0])):
                return float('inf')
            if i == len(arr)-1:
                return arr[i][j]
            return arr[i][j] + min(dp(i+1, k) for k in range(len(arr[0])) if k!=j)
        
        return min(dp(0, j) for j in range(len(arr[0])))

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(1,len(arr)):
            for j in range(len(arr[0])):
                above = []
                for k in range(len(arr[0])):
                    if k!=j:
                        heapq.heappush(above, arr[i-1][k])
                        #above.add()
                #print(above)
                #print(above)
                arr[i][j] = arr[i][j] + above[0]
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m,n=len(arr),len(arr[0])
        for i in range(1,m):
            for j in range(n):
                m=float('inf')
                for k in range(n):
                    if k==j:
                        continue
                    m=min(m,arr[i-1][k])
                arr[i][j]+=m
        return min(arr[-1])

import itertools

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int: 
        nr, nc = len(arr), len(arr[0])
        for (r_i, c_i) in itertools.product(
            list(range(nr-2,-1,-1)),
            list(range(nc))
        ):
            downs = [
                (r_i+1, d_c) for d_c in range(nc) if d_c != c_i
            ]
            min_downs = min([
                arr[d_r][d_c] for (d_r, d_c) in downs
            ])
            
            arr[r_i][c_i] += min_downs
            
        return min([
            arr[0][c] for c in range(nc)
        ])
        


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        N = len(arr)
        
        dp = [[0] * N for _ in range(N)]
        
        for i in range(N):
            dp[N-1][i] = arr[N-1][i]
        
        for r in range(N-2, -1, -1):
            for c in range(N):
                min_c = float('inf')
                for n_c in range(N):
                    if n_c == c:
                        continue
                    min_c = min(min_c, arr[r+1][n_c])
                dp[r][c] = min_c + arr[r][c]
                arr[r][c] = dp[r][c]
        
        res = float('inf')
        for i in range(N):
            res = min(res, dp[0][i])
        
        return res

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        from copy import deepcopy
        
        v=deepcopy(arr)
        
        for i in range(len(arr)-2,-1,-1):
            for j in range(len(arr[0])):
                minn=float('inf')
                for k in range(len(arr[0])):
                    if j!=k:
                        minn=min(minn,v[i+1][k])
                        
                v[i][j]+=minn
                
                
        return min(v[0])
                
                


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if len(arr)==0: return 0
        for i in range(1,len(arr)):
            for j in range(len(arr[0])):
                mini = float('inf')
                for k in range(len(arr[0])):
                    if k!=j:
                        mini = min(mini,arr[i-1][k])
                arr[i][j] += mini
        ans = float('inf')
        for i in range(len(arr[0])):
            ans = min(ans, arr[-1][i])
        return ans

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        g = [[inf]*len(a) for a in A]
        def get(i,j):
            m = inf
            for k in range(0, len(A[0])):
                if k != j:
                    m = min(m, g[i-1][k])
            return m
        for i in range(len(g)):
            for j in range(len(g[0])):
                if i == 0:
                    g[i][j] = A[i][j]
                else:
                    g[i][j] = min(g[i][j], get(i,j)+A[i][j])
        return min(g[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp=[[0 for i in range(len(arr))]for j in range(len(arr))]
        for i in range(len(arr)):
            dp[0][i]=arr[0][i]
        for i in range(1,len(arr)):
            for j in range(len(arr)):
                m=9999999
                for k in range(len(arr)):
                    if k!=j:
                        m=min(m,dp[i-1][k])
                dp[i][j]=arr[i][j]+m 
        m=99999999        
                
        for i in range(len(arr)):
            m=min(m,dp[len(arr)-1][i])
        return m    

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        min_index = 0
        secondmn_index = 0
        temp = [[0 for i in range(len(arr[0]))] for j in range(len(arr))]
        temp[0] = arr[0][:]
        for i in range(1,len(arr)):
            min_index = 0
            secondmn_index = 1
            for j in range(len(arr)):
                if temp[i-1][min_index]>temp[i-1][j]:
                    secondmn_index = min_index
                    min_index = j
                elif temp[i-1][secondmn_index]>temp[i-1][j] and j!=min_index:
                    secondmn_index = j
            for j in range(len(arr)):
                if j!=min_index:
                    temp[i][j] = arr[i][j] + temp[i-1][min_index]
                else:
                    temp[i][j] = arr[i][j] + temp[i-1][secondmn_index]
        print(temp)
        return min(temp[len(temp)-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        A = arr
        m = len(A)
        n = len(A[0])
        # dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + A[i][j]
        if m == n == 1:
            return A[0][0]
            
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                cell = float('inf')
                for k in range(1, n + 1):
                    if j == k:
                        continue
                    cell = min(cell, dp[i-1][k])
                dp[i][j] = cell + A[i-1][j-1]
                
                
        return min(dp[-1][1:])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr:
            return 0
        
        R = C = len(arr)
        
        for r in range(1, R):
            for c in range(0, C):
                
                m = float('inf')
                for i in range(C):
                    if i != c:
                        m = min(m, arr[r-1][i])
                
                arr[r][c] += m
            # print(arr[r], m)
        
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if arr is None or len(arr) == 0 or len(arr[0]) == 0: return 0
        for i in range(1,len(arr)):
            for j in range(len(arr[0])):
                temp = float('inf')
                for last_col in range(len(arr[0])):
                    if last_col != j:
                        temp = min(temp, arr[i-1][last_col])
                arr[i][j] += temp
        ans = float('inf')     
        for i in range(len(arr[0])):
            ans = min(ans, arr[-1][i])
        return ans


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        for i in range(1, n):
            for j in range(len(arr[0])):
                curMin = float('inf')
                for k in range(len(arr[0])):
                    if j == k:
                        continue
                    curMin = min(curMin, arr[i - 1][k])
                arr[i][j] += curMin
            # arr[i][1] += min(arr[i - 1][0], arr[i - 1][2])
            # arr[i][2] += min(arr[i - 1][0], arr[i - 1][1])
                
        return min(arr[n - 1])
                        
                    


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        dp = arr
        for i in range(1, m):
            for j in range(n):
                acc = float('inf')
                for k in range(n):
                    if k == j: continue
                    acc = min(acc, arr[i - 1][k])
                dp[i][j] = arr[i][j] + acc
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        import math
        n = len(arr)
        if n==0: return 0
        k = len(arr[0])
        for house in range(1,n):
            for color in range(k):
                best = math.inf
                for prev_color in range(k):
                    if color == prev_color:
                        continue
                    best = min(best, arr[house - 1][prev_color])
                arr[house][color] += best
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:

        rows = len(arr)
        columns = len(arr[0])
        for i in range(1,rows):
            for j in range(columns):
                minimum = float('inf')
                for k in range(columns):
                    if k!=j:
                        minimum = min(minimum,arr[i-1][k])
                arr[i][j] = arr[i][j] + minimum
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        for i in range(1, n):
            lowest = min(arr[i - 1])
            lowestCount = 0
            secondLowest = float('inf')
            for j in range(len(arr[0])):
                if arr[i - 1][j] == lowest:
                    lowestCount += 1
                    
                if arr[i - 1][j] > lowest:
                    secondLowest = min(secondLowest, arr[i - 1][j])
                    
            if lowestCount >= 2:
                secondLowest = lowest
            
            for j in range(len(arr[0])):
                if arr[i-1][j] == lowest:
                    arr[i][j] += secondLowest
                else:
                    arr[i][j] += lowest
                
        return min(arr[n - 1])
                        
                    


import heapq
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        copy = deepcopy(arr)
        
        for row in range(1,len(arr)):
            smallest=heapq.nsmallest(2,copy[row-1])
            for col in range(len(arr[0])):
                copy[row][col] += smallest[0] if copy[row-1][col]!=smallest[0] else smallest[1]
        return min(copy[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        if n == 1:
            return arr[0][0]
        
        MAX_V = int(1e9)
        min_v = [0] * n
        
        for i in range(n):
            row = arr[i]
            new_min_v = [MAX_V] * n
            scan_min = min_v[-1]
            for i in range(n - 2, -1, -1):
                new_min_v[i] = min(new_min_v[i], scan_min + row[i])
                scan_min = min(scan_min, min_v[i])
            scan_min = min_v[0]
            for i in range(1, n):
                new_min_v[i] = min(new_min_v[i], scan_min + row[i])
                scan_min = min(scan_min, min_v[i])
            min_v = new_min_v
        return min(min_v)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m = len(arr)
        n = len(arr[0])
        dp = [[float('inf') for j in range(n)] for i in range(m)]
        ## initialization
        for j in range(n):
            dp[0][j] = arr[0][j]
            
        for i in range(1, m):
            min_idx = sec_min_idx = None
            for j in range(n):
                if min_idx is None or dp[i-1][j]<dp[i-1][min_idx]:
                    sec_min_idx = min_idx
                    min_idx = j
                elif sec_min_idx is None or dp[i-1][j]<dp[i-1][sec_min_idx]:
                    sec_min_idx = j
                    
            # print(\"min_idx\", min_idx, \"sec_min_idx\", sec_min_idx)
            for j in range(n):
                if j == min_idx:
                    dp[i][j] = dp[i-1][sec_min_idx] + arr[i][j]
                else:
                    dp[i][j] = dp[i-1][min_idx] + arr[i][j]
                    
        return min(dp[m-1])


'''
find the minimum of the previous row and add it to the minimum of the current row if they are not in the same column

else -> add the second smallest from the previous to the min in current row

'''
import heapq
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        rows,cols = len(arr), len(arr[0])
        for i in range(1,rows):
            # find the 2 smallest value from previous row
            min1, min2 =  heapq.nsmallest(2,arr[i-1])
            '''min1 = min(arr[i-1])
            min1_index = arr[i-1].index(min1)
           
            min2 = min(x for j,x in enumerate(arr[i-1]) if j!=min1_index )'''
            for j in range(cols):
                if arr[i-1][j] == min1:
                    arr[i][j] +=min2
                else:
                    arr[i][j] +=min1
        return min(arr[-1])
            


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        dp = arr[0][:]
        for i in range(1, n):
            right_min = [math.inf]*(n-1) + [dp[n-1]]
            for j in range(n-2, -1, -1):
                right_min[j] = min(right_min[j+1], dp[j])
            left_min = math.inf
            for j in range(n):
                prev = left_min
                if j < n-1:
                    prev = min(prev, right_min[j+1])
                left_min = min(left_min, dp[j])
                dp[j] = prev + arr[i][j]
        return min(dp)


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        # always fall to the smallest or second smallest (if smallest is the same )
        
        m, n = len(arr), len(arr[0])
        i = 1
        while i < m:
            a = arr[i - 1][:]
            min1 = a.index(min(a))
            a[min1] = float('inf')
            min2 = a.index(min(a))
            a = arr[i - 1]
            for j in range(n):
                if j == min1:
                    arr[i][j] += a[min2]
                else:
                    arr[i][j] += a[min1]
            i += 1
        return min(arr[-1])
        


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        rows = len(arr)

        for row in range(1, rows):
            nsmall_in_row = heapq.nsmallest(2, arr[row - 1])
            
            for col in range(0, rows):
                arr[row][col] += nsmall_in_row[1] if nsmall_in_row[0] == arr[row - 1][col] else nsmall_in_row[0]

        return min(arr[-1])
    
    # Time complexity - O( n * (heap time + n))


import heapq
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [[float('inf')] + i + [float('inf')] for i in arr]
        for i in range(1,len(dp)):
            hp = heapq.nsmallest(2, dp[i - 1])
            for j in range(1,len(dp[0])-1):
                dp[i][j] +=  hp[0] if dp[i-1][j] != hp[0] else hp[1]
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        n=len(A)
        for i in range(n-2,-1,-1):
            mn=min(A[i+1])
            idx=A[i+1].index(mn)
            for j in range(n):
                if(j!=idx):
                    A[i][j]+=mn
                elif(j==idx):
                    dp=[101 for _ in range(n)]
                    for k in range(n):
                        if(k!=idx):
                            dp[k]=A[i+1][k]
                    A[i][j]+=min(dp)    
        return(min(A[0]))            

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        above_others = [0] * len(arr[0]) #minimum path sum not including itself
        
        for row in arr:
            paths = [n + path for n, path in zip(row, above_others)]
            others = [float(\"inf\")] * len(paths)
            
            for r in range(len(paths)), reversed(range(len(paths))):
                min_path = float('inf')
                for i in r:
                    others[i] = min(others[i], min_path)
                    min_path = min(min_path, paths[i])
            
            above_others = others
        
        return min(above_others)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = copy.deepcopy(arr)
        for i in range(1, len(dp)):
            r = heapq.nsmallest(2, dp[i-1])
            for j in range(len(dp[0])):
                dp[i][j] += r[1] if dp[i - 1][j] == r[0] else r[0]
        return min(dp[-1])


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        import heapq

        dp = arr[0][:]
        for i in range(1, len(arr)):
            heap = list((v, k) for k, v in enumerate(dp))
            heapq.heapify(heap)
            min_value, min_pos = heapq.heappop(heap)
            alter_value, _ = heapq.heappop(heap)
            new_dp = [v + min_value for v in arr[i]]
            new_dp[min_pos] += alter_value - min_value
            dp = new_dp
        return min(dp)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        def getmin(row):
            m1=float(\"inf\")
            indx1=0
            m2=float(\"inf\")
            indx2=0
            for elem in range(len(row)):
                #print(m1,m2)
                if row[elem]<=m1:
                    m2=m1
                    m1=row[elem]
                    indx2=indx1
                    indx1=elem
                elif row[elem]<m2:
                    m2=row[elem]
                    indx2=elem
            return indx1,indx2
        
        for i in range(1,len(arr)):
            col1,col2=getmin(arr[i-1])
            #print(col1,col2)
            for j in range(len(arr[0])):
                if j==col1:
                    arr[i][j]+=arr[i-1][col2]
                else:
                    arr[i][j]+=arr[i-1][col1]
        #print(arr)
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        copy = deepcopy(arr)
        
        for row in range(1,len(arr)):
            min1, ind1, min2, ind2 = 20000,0,20000,0
            for i, v in enumerate(copy[row-1]):
                if v < min1:
                    min1=v
                    ind1=i
            for i, v in enumerate(copy[row-1]):
                if v < min2 and i!=ind1:
                    min2=v
                    ind2=i
            # print(min1, ind1, min2, ind2)
            for col in range(len(arr[0])):
                copy[row][col] += copy[row-1][ind1] if ind1 != col else copy[row-1][ind2]
        return min(copy[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        def findMinOtherThanThis(nums):
            ret = list()
            left, right = [0 for i in range(len(arr))], [0 for i in range(len(arr))]
            
            left_min = float('inf')
            for idx, n in enumerate(nums):
                left[idx] = left_min
                left_min = min(left_min, n)
                
            right_min = float('inf')
            for idx in range(len(nums)-1, -1, -1):
                right[idx] = right_min
                right_min = min(right_min, nums[idx])
                
            for idx in range(len(nums)):
                ret.append(min(left[idx], right[idx]))
            
            return ret
            
        if not arr:
            return 0
        m = len(arr)
        n = len(arr[0])
        dp = [[0 for j in range(n)] for i in range(m)]
        
        for i in range(m-1, -1, -1):
            for j in range(n):
                if i == m-1:
                    dp[i][j] = arr[i][j]
                else:
                    dp[i][j] = arr[i][j] + dp[i+1][j]
            dp[i] = findMinOtherThanThis(dp[i])
        
        return min(dp[0])

\"\"\"
dp[r][c] = min(dp[r-1][c1], dp[r-1][c2]) for any c1, c2 != c

Base case:

dp[r][c] = 0 for r < 0

Complexity:

Time = r * c
\"\"\"

# TLE for top down

# class Solution:
#     def minFallingPathSum(self, arr: List[List[int]]) -> int:
#         rows, cols = len(arr), len(arr[0])
        
#         @lru_cache(None)
#         def dp(r, c):
#             if r < 0:
#                 return 0
            
#             return arr[r][c] + min(dp(r-1, c1) for c1 in range(cols) if c1 != c)
    
#         return min(dp(rows-1, c) for c in range(cols))

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        rows, cols = len(arr), len(arr[0])
        prev_row = [0] * cols
    
        for r in range(rows):
            min1, min2 = heapq.nsmallest(2, prev_row)
            prev_row = [arr[r][c] + (min1 if min1 != prev_row[c] else min2) for c in range(cols)]
        
        return min(prev_row)
                        

class Solution:
    
    
    def minFallingPathSum(self, cost: List[List[int]]) -> int:
        cols = len(cost[0])
        dp = cost[0]

        for h in range(1, len(cost)):
            prev = sorted(cost[h-1])
            for m in range(0, cols):
                cost[h][m] += prev[1] if cost[h-1][m] == prev[0] else prev[0]

                 

        return min(cost[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        for i in range(1,len(arr)):
            r = heapq.nsmallest(2, arr[i - 1])
            
            for j in range(len(arr[0])):
                arr[i][j] += r[1] if arr[i-1][j] == r[0] else r[0]
                
                
        return min(arr[-1])
            


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        from copy import deepcopy
        from heapq import heapify
        
        v=deepcopy(arr)
        
        
        for i in range(len(arr)-2,-1,-1):
            s=deepcopy(v[i+1])
            heapify(s)
            min1=s[0]
            min2=min(s[1],s[2])
            # print(min1,min2)
            for j in range(len(arr[0])):
                
                if v[i+1][j]!=min1:
                    v[i][j]+=min1
                else:
                    v[i][j]+=min2
                    
                        

                
        return min(v[0])
                
                


import heapq
import numpy as np
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        # This requires exploring all subpaths ? No I dont think so, It jus trquires an intelligent browse of the problem

        x = len(arr)
        new_count = np.zeros((x, x))
        new_count[0] = arr[0]
        for k in range(1, x):
            previous_line_maxes =  heapq.nsmallest(2, new_count[k-1])
            for index in range(len(arr)):
                if new_count[k -1][index] == previous_line_maxes[0]:
                    value_to_add = previous_line_maxes[1]
                else : 
                    value_to_add = previous_line_maxes[0]
  
                new_count[k, index] = value_to_add + arr[k][index]
    
            
        return(int(min(new_count[-1])))
        


import heapq

class Solution:
  def minFallingPathSum(self, arr: List[List[int]]) -> int:
    # O(N^2), N = len(arr) >= 3
    n = len(arr)
    # keep the min and 2nd-min with corresponding index of falling path at each row
    xm = [(0, -1), (0, -1)]
    for i in range(n):
      xm = heapq.nsmallest(2, [(x + xm[1][0], j) if j == xm[0][1] else (x + xm[0][0], j) for j, x in enumerate(arr[i])])
    return xm[0][0]

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
     
        def getTwo(a):
            pos = {v:k for k,v in enumerate(a)}
            f,s = sorted(a)[:2]
            return ([f,pos[f]],[s,pos[s]])
        
        for i in range(1,n):
            pre = getTwo(arr[i-1])
            for j in range(n):
                if j!=pre[0][1]:
                    arr[i][j]+=pre[0][0]
                else:
                    arr[i][j]+=pre[1][0]
        return min(arr[-1])

\"\"\"
dp[r][c] = min(dp[r-1][c1], dp[r-1][c2]) for any c1, c2 != c

Base case:

dp[r][c] = 0 for r < 0

Complexity:

Time = r * c
\"\"\"

# TLE for top down

# class Solution:
#     def minFallingPathSum(self, arr: List[List[int]]) -> int:
#         rows, cols = len(arr), len(arr[0])
        
#         @lru_cache(None)
#         def dp(r, c):
#             if r < 0:
#                 return 0
            
#             return arr[r][c] + min(dp(r-1, c1) for c1 in range(cols) if c1 != c)
    
#         return min(dp(rows-1, c) for c in range(cols))

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        prev_row = [0] * len(arr[0])
    
        for r in range(len(arr)):
            min1, min2 = heapq.nsmallest(2, prev_row)
            prev_row = [arr[r][c] + (min1 if min1 != prev_row[c] else min2) for c in range(len(arr[r]))]
        
        return min(prev_row)
                        

class Solution:
    
    

    
    
    def minFallingPathSum(self, A):
        for i in range(1, len(A)):
            r = heapq.nsmallest(2, A[i - 1])
            for j in range(len(A[0])):
                A[i][j] += r[1] if A[i - 1][j] == r[0] else r[0]
        return min(A[-1])

class Solution:
    def minFallingPathSum(self, dp: List[List[int]]) -> int:
        for i in range(1, len(dp)):
            best2 = sorted(list(enumerate(dp[i-1])), key=lambda x: x[1])[:2]
            for j in range(len(dp[i])):
                dp[i][j] = [x for x in best2 if x[0] != j][0][1] + dp[i][j]

        return min(dp[-1])

class Solution:
    def scan(self, row: List[int], n: int) -> (int, int, int):
        best = None
        k = None
        alt = None
        for j in range(n):
            if not best or row[j] < best:
                alt = best
                best = row[j]
                k = j
            elif not alt or row[j] < alt:
                alt = row[j]
        return best, k, alt
    
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        M = [[None for j in range(n)] for i in range(n)]

        for j in range(n):
            M[0][j] = arr[0][j]
        best, k, alt = self.scan(M[0], n)

        for i in range(1, n):
            for j in range(n):
                if j != k:
                    M[i][j] = arr[i][j] + best
                else:
                    M[i][j] = arr[i][j] + alt
            best, k, alt = self.scan(M[i], n)
        
        return best

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m, n = len(arr), len(arr[0])
        dp = [[float(\"inf\") for _ in range(n)] for _ in range(m)]
        for j in range(n):
            dp[0][j] = arr[0][j]
        for i in range(1, m):
            first_min, second_min = float(\"inf\"), dp[i-1][0]
            first_idx, second_idx = 0, 0
            for j in range(n):
                if dp[i-1][j] < first_min:
                    first_min, second_min = dp[i-1][j], first_min
                    first_idx, second_idx = j, first_idx
                elif dp[i-1][j] < second_min:
                    second_min = dp[i-1][j]
                    second_idx = j
            for j in range(n):
                if j == first_idx:
                    dp[i][j] = second_min + arr[i][j]
                else:
                    dp[i][j] = first_min + arr[i][j]
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        iMax = len(arr)
        jMax = len(arr[0])
        
        # sortedIndex = [sorted([(arr[i][j], j) for j in range(jMax)]) for i in range(iMax)]
        dp = {}
        smallest2 = [None for _ in range(iMax)]
        
        def moveDown(preJ, iNow):
            if iNow == iMax:
                return 0

            if (preJ, iNow) in dp:
                return dp[(preJ, iNow)]
            subAns = float('inf')
            if smallest2[iNow] == None:
                temp1 = float('inf')
                temp1Index = None
                temp2 = float('inf')
                temp2Index = None
                for j, val in enumerate(arr[iNow]):
                    subAns = val + moveDown(j, iNow+1)
                    if subAns <= temp1:
                        temp1, temp2 = subAns, temp1
                        temp1Index, temp2Index = j, temp1Index
                    elif subAns <= temp2:
                        temp2 = subAns
                        temp2Index = j
                smallest2[iNow] = [[temp1Index, temp1], [temp2Index, temp2]]
                
            if preJ == smallest2[iNow][0][0]:
                subAns = smallest2[iNow][1][1]
            else:
                subAns = smallest2[iNow][0][1]
            dp[(preJ, iNow)] = subAns
            return subAns
        return moveDown(-1, 0)


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n= len(arr)
        for i in range(1, n):
            r= heapq.nsmallest(2, arr[i-1])
            for j in range(n):
                arr[i][j]+= r[1] if arr[i-1][j]== r[0] else r[0]
                
        return min(arr[-1])

class Solution:
    def minFallingPathSum1(self, arr: List[List[int]]) -> int:
        '''
        Time: O(mn^2)  - due linear search for min in inner loop
        Space: O(n + n) ~ O(n)
        '''
        m = len(arr)
        n = len(arr[0])
        
        if m == 1: # 1 ele sq. matrix
            return arr[0][0]
        
        def get_min_neighbors(j):
            a, row_prev[j] = row_prev[j], float('inf')
            min_val = min(row_prev)
            row_prev[j] = a
            return min_val
        
        row_prev = arr[0]
        cur = [0]*n
        global_min = float('inf')
        
        for row in range(1, m):
            for col in range(n):
                cur[col] = get_min_neighbors(col) + arr[row][col]
                
                if row == m-1 and cur[col] < global_min:
                    global_min = cur[col]
     
            row_prev = cur[:]
        
        return global_min

    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        '''
        Time: O(mn) - if heapq.nsmallest is linear, here min search is in outer loop
        Space: O(n + n) ~ O(n)
        '''
        m = len(arr)
        n = len(arr[0])
        
        if m == 1: # 1 ele sq. matrix
            return arr[0][0]
        
        def get_min_neighbors():
            #min1, min2 = heapq.nsmallest(2, row_prev) #also works
            min1 = float('inf')
            min2 = float('inf')
            
            for val in dp:
                if val < min1:
                    min2 = min1
                    min1 = val
                elif val < min2:
                    min2 = val
                    
            return min1, min2
        
        dp = arr[0]
        cur = [0]*n
        global_min = float('inf')
        
        for row in range(1, m):
            min1, min2 = get_min_neighbors()
            for col in range(n):
                min_val = min1 if dp[col] != min1 else min2 #doesnt matter if duplicates
                cur[col] = min_val + arr[row][col] 
                
                if row == m-1 and cur[col] < global_min:
                    global_min = cur[col]
     
            dp = cur[:]

        return global_min

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(1, len(arr)):
            r = heapq.nsmallest(2, arr[i - 1])
            for j in range(len(arr[0])):
                arr[i][j] += r[1] if arr[i-1][j] == r[0] else r[0]
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        iMax = len(arr)
        jMax = len(arr[0])
        
        # sortedIndex = [sorted([(arr[i][j], j) for j in range(jMax)]) for i in range(iMax)]
        dp = {}
        smallest2 = [None for _ in range(iMax)]
        
        def moveDown(preJ, iNow):
            if iNow == iMax:
                return 0

            if (preJ, iNow) in dp:
                return dp[(preJ, iNow)]
            subAns = float('inf')
            if smallest2[iNow] == None:
                temp1 = float('inf')
                temp1Index = None
                temp2 = float('inf')
                temp2Index = None
                for j, val in enumerate(arr[iNow]):
                    subAns = val + moveDown(j, iNow+1)
                    if subAns <= temp1:
                        temp1, temp2 = subAns, temp1
                        temp1Index, temp2Index = j, temp1Index
                    elif subAns <= temp2:
                        temp2 = subAns
                        temp2Index = j
                smallest2[iNow] = [[temp1Index, temp1], [temp2Index, temp2]]
                
            if preJ == smallest2[iNow][0][0]:
                subAns = smallest2[iNow][1][1]
            else:
                subAns = smallest2[iNow][0][1]
            dp[(preJ, iNow)] = subAns
            return subAns
        return moveDown(-1, 0)
    
#         iMax = len(arr)
#         jMax = len(arr[0])
        
#         # sortedIndex = [sorted([(arr[i][j], j) for j in range(jMax)]) for i in range(iMax)]
#         # print(sortedIndex)
#         dp = {}
#         dp2 = {}
#         ans = [float('inf')]
        
#         def moveDown(preJ, iNow, sumNow):
#             if iNow == iMax:
#                 ans[0] = min(ans[0], sumNow)
#                 return 0

#             if (preJ, iNow) in dp and dp[(preJ, iNow)] <= sumNow:
#                 ans[0] = min(ans[0], sumNow +  dp2[(preJ, iNow)])
#                 return dp2[(preJ, iNow)]
#             # if (preJ, iNow) in dp2:
#             #     ans[0] = min(ans[0], sumNow +  dp2[(preJ, iNow)])
#             #     return dp2[(preJ, iNow)]
#             dp[(preJ, iNow)] = sumNow
#             # if sumNow >= ans[0]:
#             #     return float('inf')
#             subAns = float('inf')
#             # for val,j in (sortedIndex[iNow]):
#             for j, val in enumerate(arr[iNow]):
#                 if j != preJ:
#                     subAns = min(subAns, val + moveDown(j, iNow+1, val+sumNow))
#                     # moveDown(j, iNow+1, val+sumNow)
                    
#             dp2[(preJ, iNow)] = subAns
#             return subAns
#         moveDown(-1, 0, 0)
#         return ans[0]


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m = len(arr)
        n = len(arr[0])
        dp = [[0]*n for i in range(m)]

        for j in range(n):
            dp[0][j] = arr[0][j]

        for i in range(1,m):
            sorted_lastrow = sorted([(k, dp[i - 1][k]) for k in range(n)], key=lambda x: x[1])
            p_index, p = sorted_lastrow[0]
            q_index, q = sorted_lastrow[1]
            
            for j in range(n):

                

                lastdp = p if p_index != j else q
                dp[i][j] = lastdp + arr[i][j]

        return min(dp[m-1])


class Solution:
    def minFallingPathSum1(self, arr: List[List[int]]) -> int:
        '''
        Time: O(mn^2)  - due linear search for min in inner loop
        Space: O(n + n) ~ O(n)
        '''
        m = len(arr)
        n = len(arr[0])
        
        if m == 1: # 1 ele sq. matrix
            return arr[0][0]
        
        def get_min_neighbors(j):
            a, row_prev[j] = row_prev[j], float('inf')
            min_val = min(row_prev)
            row_prev[j] = a
            return min_val
        
        row_prev = arr[0]
        cur = [0]*n
        global_min = float('inf')
        
        for row in range(1, m):
            for col in range(n):
                cur[col] = get_min_neighbors(col) + arr[row][col]
                
                if row == m-1 and cur[col] < global_min:
                    global_min = cur[col]
     
            row_prev = cur[:]
        
        return global_min

    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        '''
        Time: O(mn) - if heapq.nsmallest is linear, here min search is in outer loop
        Space: O(n + n) ~ O(n)
        '''
        m = len(arr)
        n = len(arr[0])
        
        if m == 1: # 1 ele sq. matrix
            return arr[0][0]
        
        def get_min_neighbors():
            min1, min2 = heapq.nsmallest(2, row_prev)
            return min1, min2
        
        row_prev = arr[0]
        cur = [0]*n
        global_min = float('inf')
        
        for row in range(1, m):
            min1, min2 = get_min_neighbors() #if linear
            for col in range(n):
                min_val = min1 if row_prev[col] != min1 else min2 #doesnt matter if duplicates
                cur[col] = min_val + arr[row][col] 
                
                if row == m-1 and cur[col] < global_min:
                    global_min = cur[col]
     
            row_prev = cur[:]

        return global_min

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        if n == 1:
            return arr[0][0]
        
        \"\"\"
        Returns the tuples (fp_sum, fp_sum_2) each of the form
        (col, value) where col is the col the falling path sum
        starts from and value is the falling path sum's value.
        fp_sum is the true min falling path sum for the row and
        fp_sum_2 is the SECOND-to-min falling path sum for the
        row. That way we can guarantee an optimal continuation
        for the row before since the element with the same col
        as fp_sum can just continue locally with fp_sum_2.
        \"\"\"
        @lru_cache(maxsize=None)
        def min_fp_sums(row):
            fp_sum, fp_sum_2 = ((-1, 0), (-1, 0)) if row == n - 1 else min_fp_sums(row + 1)
            min_fp_sum, min_fp_sum_2 = ((-1, math.inf), (-1, math.inf))
            for col, num in enumerate(arr[row]):
                value = num + (fp_sum if col != fp_sum[0] else fp_sum_2)[1]
                if value < min_fp_sum[1]:
                    min_fp_sum_2 = min_fp_sum
                    min_fp_sum = (col, value)
                elif value < min_fp_sum_2[1]:
                    min_fp_sum_2 = (col, value)
            return min_fp_sum, min_fp_sum_2
            
        return min_fp_sums(0)[0][1]

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m = len(arr[0])
        table = [arr[0][i] for i in range(m)]
        
        def get_mins(table):
            cur_min = int(1e+9)
            cur_min_i = -1
            next_cur_min = int(1e+9)
            next_cur_min_i = -1
            for i, x in enumerate(table):
                if x <= cur_min:
                    cur_min, cur_min_i = x, i
            for i, x in enumerate(table):
                if x <= next_cur_min and i != cur_min_i:
                    next_cur_min, next_cur_min_i = x, i
            return cur_min, cur_min_i, next_cur_min, next_cur_min_i 
        
        cur_min, cur_min_i, next_cur_min, next_cur_min_i = get_mins(table)
        for i in range(1, len(arr)):
            for j in range(m):
                table[j] = arr[i][j]
                if j != cur_min_i:
                    table[j] = arr[i][j] + cur_min
                else:
                    table[j] = arr[i][j] + next_cur_min
            cur_min, cur_min_i, next_cur_min, next_cur_min_i = get_mins(table)
        return cur_min


import numpy as np
class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        if len(arr)==1: return min(arr[0])
        
        if len(arr[0])==2:
            return (min(arr[0][1]+arr[1][0], arr[0][0]+arr[1][1]))
        
        # arr = np.random.sample((6,6))
        
        # find the smallest 3 of the index
        sml = -np.ones((len(arr)+1, 3))
        for i in range(len(arr)):
            r = np.array(arr[i])
            sml[i+1] = (np.argsort(r)[:3])
        # print (sml)
        
        
        dp = np.zeros((len(arr)+1, 3))
        for i in range(1, len(arr)+1):
            for j in range(3):
                # print(i,j)
                col_idx = int(sml[i][j])
                sml_idx = [idx for idx in range(3) if sml[i-1][idx] != col_idx]
                # print (col_idx, sml_idx)
                # find the smallest of the last row
                # print (arr[i-1][(col_idx)])
                # print ([dp[i-1][c] for c in sml_idx])
                dp[i][j] = arr[i-1][(col_idx)] + min([dp[i-1][c] for c in sml_idx])

        print((dp[-1]))
        return int(min(dp[-1]))


class Solution:
    def minFallingPathSum(self, dp: List[List[int]]) -> int:
        for i in range(1, len(dp)):
            best2 = heapq.nsmallest(2, list(enumerate(dp[i-1])), key=lambda x: x[1])
            for j in range(len(dp[i])):
                dp[i][j] = [x for x in best2 if x[0] != j][0][1] + dp[i][j]

        return min(dp[-1])

from heapq import nsmallest


class Solution:
    def minFallingPathSum(self, arr) -> int:
        \"\"\"
        Given a square matrix of integers, this program uses dynamic
        programming to determine the minimum falling path sum following
        the rule that the values chosen from consecutive rows cannot be
        from the same column.

        :param arr: square matrix of integers
        :type arr: list[list[int]]
        :return: minimum falling path sum
        :rtype: int
        \"\"\"

        \"\"\"
        Initialize:
        - Number of rows (rows) and number of columns (cols) are the
          same value for a square matrix.
        - Return quickly with the result when matrix is 1 x 1. 
        \"\"\"
        rows = len(arr)
        cols = rows
        if rows == 1:
            return arr[0][0]

        \"\"\"
        Dynamic Programming:
        - Overwrite the arr matrix
        - Compute a falling path sum for each element in a row
          using the falling path sums from the previous row.
        - Use the minimum path sum from the previous row unless
          it is in the column, in which case use the second
          minimum path sum.
        - Return the minimum path sum in the bottom row as the answer.
        \"\"\"
        for row in range(1, rows):
            min_path_sum, min_path_sum_2nd = nsmallest(2, arr[row - 1])
            for col in range(cols):
                if arr[row - 1][col] == min_path_sum:
                    arr[row][col] += min_path_sum_2nd
                else:
                    arr[row][col] += min_path_sum
        return min(arr[rows - 1])


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        m=len(arr)
        
        for i in range(1,m):
            min1=min(arr[i-1])
            ind=arr[i-1].index(min1)
            for j in range(m):
                if ind==j:
                    arr[i][j]=arr[i][j]+min(arr[i-1][0:j]+arr[i-1][j+1:])
                else:
                    arr[i][j]=arr[i][j]+min1
        return min(arr[-1])

from collections import Counter
class Solution:
    def get_minset(self, l):
        left = []
        right = []
        n = len(l)
        for i in range(n):
            if i == 0:
                left.append(l[i])
                right.append(l[n-i-1])
            else:
                left.append(min(left[-1], l[i]))
                right.append(min(right[-1], l[n-i-1]))
        right = right[::-1]
        res = []
        for i in range(n):
            if i == 0:
                res.append(right[1])
            elif i == n-1:
                res.append(left[n-2])
            else:
                res.append(min(left[i-1], right[i+1]))
        return res

    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        last = arr[0]
        maxset = self.get_minset(last)
        for i in range(1, len(arr)):
            tmp = []
            for j in range(len(arr[0])):
                tmp.append(maxset[j]+arr[i][j])
            last = tmp
            maxset = self.get_minset(last)
        return min(last)
                
                


class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        for i in range(1, len(A)):
            for j in range(len(A)):
                
                temp = A[i-1][j]
                A[i-1][j] = float(\"Inf\")
                A[i][j] += min(A[i-1])
                A[i-1][j] = temp
        return min(A[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        '''
        Time: O(mn)
        Space: O(n + n) ~ O(n)
        '''
        m = len(arr)
        n = len(arr[0])
        
        if m == 1: # 1 ele sq. matrix
            return arr[0][0]
        
        def get_min_neighbors(i, j):
            a, row_prev[j] = row_prev[j], float('inf')
            min_val = min(row_prev)
            row_prev[j] = a
            return min_val
        
        row_prev = arr[0]
        cur = [0]*n
        global_min = float('inf')
        
        for row in range(1, m):
            for col in range(n):
                cur[col] = get_min_neighbors(row, col) + arr[row][col]
                
                if row == m-1 and cur[col] < global_min:
                    global_min = cur[col]
     
            row_prev = cur[:]
        
        return global_min

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        m = 100 * len(arr)
        T = [[0 for _ in range(len(arr))] for _ in range(len(arr))]
        T[0] = arr[0]
        for i in range(1, len(arr)):
            for j in range(len(arr)):
                temp = T[i-1][j]
                T[i-1][j] = m
                T[i][j] = arr[i][j] + min(T[i-1])
                T[i-1][j] = temp
        return min(T[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        inf=2000000000
        m, n = len(arr), len(arr[0])
        res = [[inf]*n for _ in range(m)]
        res[0] = arr[0]
        for i in range(1, m):
            for j in range(n):
                last = min(res[i-1][:j]) if j > 0 else inf
                last = min(last,min(res[i-1][j+1:])) if j < n - 1 else last
                res[i][j] = last + arr[i][j] 
        print(res)
        return min(res[-1])

class Solution(object):
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        N = len(A)
        
        # init dp array (dp[i][j] min sum from i,j forward)
        dp = [[0 for i in range(N)] for j in range(N)]
        
        # init last row of dp (base case)
        for j in range(N):
            dp[-1][j] = A[-1][j]
            
        for i in range(N-2, -1, -1):
            for j in range(N):
                if j == 0:
                    # left column
                    dp[i][j] = A[i][j] + min(dp[i+1][1:])
                elif j == N-1:
                    # right column
                    dp[i][j] = A[i][j] + min(dp[i+1][:-1])
                else:
                    # not border column
                    dp[i][j] = A[i][j] + min(dp[i+1][:j]+dp[i+1][j+1:])
        
        print(dp)
        return min(dp[0])

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        
        if len(A)==1:
            return min(A[0])
        
        for i in range(1, len(A)):
            
            minValue, minIdx = sys.maxsize, -1
            secondMinValue = sys.maxsize
            for j in range(len(A[0])): 
                if A[i-1][j] < minValue: 
                    secondMinValue = minValue
                    minValue, minIdx  = A[i-1][j], j
                elif A[i-1][j] < secondMinValue: 
                    secondMinValue = A[i-1][j]
            for j in range(len(A[0])):
                if j==minIdx: 
                    A[i][j] += secondMinValue
                else: 
                    A[i][j] += minValue 
                    
        return min(A[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = [0] * len(arr[0])
        for r, row in enumerate(arr):
            for c in range(len(row)):
                row[c] += min(dp[:c]+dp[c+1:])
            dp = row[:]
        return min(dp)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        m = len(arr[0])
        res = 0
        for i in range(1, n):
            for j in range(m):
                arr[i][j] += min(arr[i-1][0:j] + arr[i-1][j+1:])
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        dp = [[0 for i in range(n)] for i in range(n)]
        for i in range(n):
            dp[0][i] = arr[0][i]
        for i in range(1,n):
            dp[i][0] = min(dp[i-1][1:]) + arr[i][0]
            for j in range(1,n-1):
                minLeft = min(dp[i-1][:j])
                minRight = min(dp[i-1][(j+1):])
                dp[i][j] = min(minLeft,minRight) + arr[i][j]
            dp[i][-1] = min(dp[i-1][:(-1)]) + arr[i][-1]
        return min(dp[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        m = len(arr[0])
        for i in range(1,n):
            for j in range(m):
                arr[i][j] += min(arr[i-1][0:j]+arr[i-1][j+1:])
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        for i in range(1, len(arr)):
            for j in range(len(arr[0])):
                
                # if j == 0:
                arr[i][j] += min(arr[i - 1][:j] + arr[i - 1][j + 1 :])
                
#                 elif j == len(A[0]) - 1:
#                     A[i][j] += min()
                    
#                 else:
#                     A[i][j] += min()
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        # find all falling path?: must be TLE
        # recursive with memo: also TLE, in O(n^2) time complexity
        # helper(i, j): we are looking at jth row and its last row , we choose col: i
        
#         self.dic = {}
#         def helper(i, j):
#             if (i, j) in self.dic:
#                 return self.dic[(i, j)]
            
#             if j == len(arr) -1:
#                 res =  min(arr[-1][0:i]+arr[-1][i+1:])
#                 self.dic[(i, j)] = res
#                 return res
            
            
#             res = math.inf
            
#             for c in range(len(arr)):
#                 if c != i:
#                     res = min(res, helper(c, j+1) + arr[j][c])
#             self.dic[(i, j)] = res
#             return res
        
#         res =  helper(-1, 0)
            
#         print(self.dic)
#         return res
        \"\"\"
            try dp also square complexity...
            dp[i][j] choose jth col in ith row
        \"\"\" 
        l = len(arr)
        dp = [[0]*len(arr) for _ in range(len(arr))]
        for i in range(l):
            dp[-1][i] = arr[-1][i]
        print(dp)
        res = inf
        for i in range((l-2), -1, -1):
            for j in range(l):
                dp[i][j] = min(dp[i+1][0:j] + dp[i+1][j+1:]) + arr[i][j]
        return min(dp[0])
        

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(1,len(arr)):
            for j in range(len(arr[0])):
                arr[i][j] += min(arr[i - 1][:j] + arr[i - 1][j + 1:])
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        for i in range(1, len(arr)):
            for j in range(len(arr[0])):
                
                # if j == 0:
                arr[i][j] += min(arr[i - 1][:j] + arr[i - 1][j + 1 :])
                
#                 elif j == len(A[0]) - 1:
#                     A[i][j] += min()
                    
#                 else:
#                     A[i][j] += min()

        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        n = len(arr)
        
        dp = [([0] * n) for _ in range(n)]
        dp[0] = arr[0]
        
        for i in range(1, n):
            for j in range(n):
                dp[i][j] = arr[i][j] + min(dp[i-1][:j] + dp[i-1][j+1:])
                
        return min(dp[-1])

class Solution:
    def find_smallest_and_second_smallest(self,a):
        smallest = a[0]
        c = 1
        for i in a:
            if i<smallest:
                smallest = i
                c = 1
            if i==smallest:
                c+=1
        smallest2 = True
        if c==2:
            smallest2 = 999999
            for i in a:
                if i!=smallest:
                    smallest2 = min(smallest2,i)
        return smallest, smallest2

    def givedp(self,arr):
        if len(arr)==1:
            return min(arr[0])
        a,b = '',''
        for i in range(len(arr)-1,-1,-1):
            if i!=len(arr)-1:
                for j in range(len(arr[i])):
                    if a==arr[i+1][j] and b!=True:
                        arr[i][j]+=b
                    else:
                        arr[i][j]+=a
            if i!=0:
                a,b = self.find_smallest_and_second_smallest(arr[i])
        return min(arr[0])
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        return self.givedp(arr)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        '''
        Time: O(mn)
        Space: O(n + n) ~ O(n)
        '''
        m = len(arr)
        n = len(arr[0])
        
        if m == 1: # 1 ele sq. matrix
            return arr[0][0]
        
        def get_min_neighbors(i, j):
            a, row_prev[j] = row_prev[j], float('inf')
            min_val = min(row_prev)
            row_prev[j] = a
            return min_val
        
        
        row_prev = arr[0]
        cur = [0]*n
        global_min = float('inf')
        
        for row in range(1, m):
            for col in range(n):
                cur[col] = get_min_neighbors(row, col) + arr[row][col]
                
                if row == m-1 and cur[col] < global_min:
                    global_min = cur[col]
     
            row_prev = cur[:]
        
        return global_min

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr:
            return 0

        prev = arr[0]
        curr = [0 for i in range(len(prev))]

        for cost in arr[1:]:
            for i in range(len(cost)):
                tmp = prev[:i] + prev[i + 1:]
                curr[i] = min(tmp) + cost[i]
            prev[:] = curr[:]

        return min(prev)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if not arr:
            return 0

        prev = arr[0]
        curr = [0 for i in range(len(prev))]

        for item in arr[1:]:
            for i in range(len(item)):
                curr[i] = min(prev[:i] + prev[i + 1:]) + item[i]
            prev[:] = curr[:]

        return min(prev)


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        N = len(arr)
        while len(arr) >= 2:
            cur = arr.pop()
            for i in range(N):
                newa = cur[:i] + cur[i+1:]
                arr[-1][i] += min(newa)
        
        return min(arr[0])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
      while(len(arr)>=2):
            row = arr.pop()
            for i in range(len(row)):
                r = row[:i]+row[i+1:]
                arr[-1][i] += min(r)
      return min(arr[0])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = arr[0][:]

        for i, costs in enumerate(arr[1:], 1):
            prev = dp[:]
            
            for j, cost in enumerate(costs):
                dp[j] = cost + min(prev[:j] + prev[j+1:])

        return min(dp)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(len(arr)-2, -1, -1):
            for j in range(len(arr[0])):
                arr[i][j] += min(arr[i+1][:j] + arr[i+1][j+1:])
        return min(arr[0])

class Solution:
    def minFallingPathSum(self, A: List[List[int]]) -> int:
        n = len(A)
        dp = [[0 for j in range(n)] for i in range(n)]
        for i in range(n):
            dp[-1][i] = A[-1][i]
        for i in range(n-2,-1,-1):
            for j in range(n):
                dp[i][j] = A[i][j] + min(dp[i+1][:j]+dp[i+1][j+1:])
        return min(dp[0])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        num_rows = len(arr)
        num_cols = len(arr[0])
        dp = [[float('inf') for _ in range(num_cols)] for _ in range(num_rows + 1)] # min cost up to pos
        
        for col in range(num_cols):
            dp[0][col] = 0
        
        for row in range(num_rows):
            dp_r = row + 1
            for col in range(num_cols):
                dp[dp_r][col] = min(dp[dp_r - 1][:col] + dp[dp_r - 1][col + 1:]) + arr[row][col]
            
        
        return min(dp[-1])
            


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        n = len(arr)
        d = [[float('-inf') for _ in range(n)] for _ in range(n)]
        for y in range(n):
            d[0][y] = arr[0][y]

        for x in range(1, n):
            smallest_two = heapq.nsmallest(2, d[x - 1])
            for y in range(n):
                if d[x - 1][y] == smallest_two[0]:
                    d[x][y] = smallest_two[1] + arr[x][y]
                else:
                    d[x][y] = smallest_two[0] + arr[x][y]

        ans = float('inf')
        for y in range(n):
            ans = min(ans, d[n - 1][y])
        return ans

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        if len(arr) ==1:
            return arr[0][0]
        else:
            Row = len(arr)
            Col = len(arr[0])
            ResultMat = [arr[0]] 
            for i in range(1,Row):
                ResultList = []
                for j in range(Col):
                    NewList= ResultMat[i-1]
                    NewList = NewList[0:j] + NewList[(j+1):len(NewList)]
                    Min = min(NewList)
                    Value = Min+arr[i][j]
                    ResultList.append(Value)
                ResultMat.append(ResultList)
            return min(ResultMat[Row-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        for i in range(1,len(arr)):
            for j in range(len(arr[0])):
                arr[i][j] += min(arr[i - 1][:j] + arr[i - 1][j + 1:])
        
        return min(arr[-1])

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        dp = arr[0]
        n = len(arr[0])
        for row in arr[1:]:
            newdp = row[:]
            for i in range(n):
                temp = dp[:i]+dp[i+1:]
                newdp[i]+=min(temp)
            dp = newdp
        return min(dp)

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        
        nr = len(arr)
        nc = len(arr[0])
        
        store = arr[:]
        
        result = 0
        
        for i in range(nr):
            
            for j in range(nc):
                
                if i >0:
                    
                    store[i][j] = min(store[i-1][:j]+ store[i-1][j+1:] )+ arr[i][j]
            
                    
                
        print(store)
        
        return min(store[nr-1])
        


class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        min_path = float(\"inf\")
        n = len(arr)
        m = len(arr[0])
        for r in range(1, n):
            min_path = float(\"inf\")
            for c in range(0, m):
                if (c == 0):
                    arr[r][c] += min(arr[r-1][1:])
                elif(c == m):
                    arr[r][c] += min(arr[r-1][:-1])
                else:
                    arr[r][c] += min(arr[r-1][:c]+arr[r-1][c+1:])
                min_path = min(min_path, arr[r][c])

        return min_path
                                
                                 
        
                                 

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        min_path = float(\"inf\")
        n = len(arr)
        m = len(arr[0])
        for r in range(1, n):
            min_path = float(\"inf\")
            for c in range(0, m):
                arr[r][c] += min(arr[r-1][:c]+arr[r-1][c+1:])
                min_path = min(min_path, arr[r][c])

        return min_path
                                
                                 
        
                                 

class Solution:
    def minFallingPathSum(self, arr: List[List[int]]) -> int:
        min_path = float(\"inf\")
        for r in range(1, len(arr)):
            min_path = float(\"inf\")
            for c in range(0, len(arr[0])):
                if (c == 0):
                    arr[r][c] += min(arr[r-1][1:])
                elif(c == len(arr[0])):
                    arr[r][c] += min(arr[r-1][:-1])
                else:
                    arr[r][c] += min(arr[r-1][:c]+arr[r-1][c+1:])
                min_path = min(min_path, arr[r][c])

        return min_path