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

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Dynamic programming

Data structures

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]
			dp = row[:]
		return min(dp)


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:
		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)


class Solution:

	def minFallingPathSum(self, arr: List[List[int]]) -> int:
		(nRow, nCol) = (len(arr), len(arr[0]))
		pathSum = arr.copy()
		for row in range(-2, -nCol - 1, -1):
			for col in range(nCol):
				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:
		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:
		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:
		m = len(arr)
		n = len(arr[0])
		if m == 1:
			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:
		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:
		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]
		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


class Solution:

	def minFallingPathSum(self, arr: List[List[int]]) -> int:
		(m, n) = (len(arr), len(arr[0]))
		for i in range(1, m):
			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 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:

		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)


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, 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:
		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, 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 j in range(n):
				prevNonAdj = [arr[i - 1][k] for k in range(n) if k != j]
				arr[i][j] += min(prevNonAdj)
		return min(arr[n - 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:
		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, 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])


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
[[-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:
		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, 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, 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, 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])
				arr[i][j] = arr[i][j] + min(above)
		return min(arr[-1])


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])


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])
		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):
			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)
		return min(arr[-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:
		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:
					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:
					dp[i][j] = min((arr[i][j] + dp[i - 1][k] for k in range(len(dp[i]) - 1)))
				else:
					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])


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:

		@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:
		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)))


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])
				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, 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:
		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
		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:
		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(1000000000.0)
		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)]
		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
			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])


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):
			(min1, min2) = heapq.nsmallest(2, arr[i - 1])
			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:
		(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])


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:
		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:
		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
			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])


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:
		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])
			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:
		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:
		n = len(arr)
		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])


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:
		iMax = len(arr)
		jMax = len(arr[0])
		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 minFallingPathSum1(self, arr: List[List[int]]) -> int:
		m = len(arr)
		n = len(arr[0])
		if m == 1:
			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:
		m = len(arr)
		n = len(arr[0])
		if m == 1:
			return arr[0][0]

		def get_min_neighbors():
			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
				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:
		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 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(1000000000.0)
			cur_min_i = -1
			next_cur_min = int(1000000000.0)
			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])
		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]
		dp = np.zeros((len(arr) + 1, 3))
		for i in range(1, len(arr) + 1):
			for j in range(3):
				col_idx = int(sml[i][j])
				sml_idx = [idx for idx in range(3) if sml[i - 1][idx] != col_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, 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, 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)
		dp = [[0 for i in range(N)] for j in range(N)]
		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:
					dp[i][j] = A[i][j] + min(dp[i + 1][1:])
				elif j == N - 1:
					dp[i][j] = A[i][j] + min(dp[i + 1][:-1])
				else:
					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)
		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 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:
		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:
		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, 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)]
		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:
		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])