Given a NxM binary matrix consisting of 0s and 1s. Find if there exists a rectangle/ square within the matrix whose all four corners are 1. 
Example 1:
Input:
N = 4, M = 5
matrix[][] = 
{
{1 0 0 1 0},
{0 0 1 0 1},
{0 0 0 1 0}, 
{1 0 1 0 1}
} 
Output: Yes
Explanation:
Valid corners are at index (1,2), (1,4), (3,2), (3,4) 
Example 2:
Input:
N = 3, M = 3
matrix[][] = 
{{0 0 0},
{0 0 0},
{0 0 0}}
Output: No
Your Task:
You don't need to take input or print anything. Complete the function ValidCorners() that takes the given matrix as input parameter and returns a boolean value.
Constraints:
1 <= R, C <= 200
0 <= A[i] <= 1

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:    

    def ValidCorner(self,matrix): 

        # Your code goes here 

Solutions:
class Solution:

	def ValidCorner(self, matrix):
		m = len(matrix[0])
		n = len(matrix)
		for i in range(n):
			d = [0] * m
			for j in range(m):
				d[j] = matrix[i][j]
			for k in range(i + 1, n):
				cnt = 0
				for j in range(m):
					if matrix[k][j] == 1 and d[j] == 1:
						cnt += 1
					if cnt == 2:
						return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		d = {}
		n = len(matrix)
		m = len(matrix[0])
		for h in range(n):
			d[h] = set()
			for g in range(m):
				if matrix[h][g] == 1:
					d[h].add(g)
			for y in range(h - 1, -1, -1):
				if len(d[h].intersection(d[y])) >= 2:
					return True


class Solution:

	def ValidCorner(self, matrix):
		n = len(matrix)
		dic = []
		m = len(matrix[0])
		for i in range(n):
			row = []
			for j in range(m):
				if matrix[i][j] == 1:
					row.append(j)
				else:
					continue
			dic.append(row)
		l = len(dic)
		for i in range(l - 1):
			arr = dic[i]
			for j in range(i + 1, l):
				count = 0
				for ele in arr:
					for ele1 in dic[j]:
						if ele == ele1:
							count += 1
						if ele < ele1:
							break
				if count >= 2:
					return 1
		return 0


class Solution:

	def ValidCorner(self, matrix):
		rows = len(matrix)
		if rows == 0:
			return False
		columns = len(matrix[0])
		table = {}
		for i in range(rows):
			for j in range(columns - 1):
				for k in range(j + 1, columns):
					if matrix[i][j] == 1 and matrix[i][k] == 1:
						if j in table and k in table[j]:
							return True
						if k in table and j in table[k]:
							return True
						if j not in table:
							table[j] = set()
						if k not in table:
							table[k] = set()
						table[j].add(k)
						table[k].add(j)
		return False


class Solution:

	def ValidCorner(self, matrix):
		if not len(matrix) or not len(matrix[0]):
			return False

		def is_all_ones_rect(upper_left_row, upper_left_col, width, height):
			return matrix[upper_left_row][upper_left_col] and matrix[upper_left_row][upper_left_col + width] and matrix[upper_left_row + height][upper_left_col] and matrix[upper_left_row + height][upper_left_col + width]
		(nrows, ncols) = (len(matrix), len(matrix[0]))
		for upper_left_row in range(nrows - 1):
			for upper_left_col in range(ncols - 1):
				for width in range(1, ncols - upper_left_col):
					for height in range(1, nrows - upper_left_row):
						if is_all_ones_rect(upper_left_row, upper_left_col, width, height):
							return True
		return False


class Solution:

	def find(self, g1, g2, k, i, j, ior, jor):
		if k == 0 and i == ior and (j == jor):
			return True
		if k == 0:
			return False
		if k != 0 and k < 4 and (i == ior) and (j == jor):
			return False
		if k % 2 == 0:
			a = False
			for l in g1[i]:
				a = a or self.find(g1, g2, k - 1, i, l, ior, jor)
			return a
		if k % 2 != 0:
			a = False
			for l in g2[j]:
				a = a or self.find(g1, g2, k - 1, l, j, ior, jor)
			return a

	def ValidCorner(self, mat):
		grow = dict()
		gcolumn = dict()
		for i in range(len(mat)):
			for j in range(len(mat[i])):
				if mat[i][j] == 1:
					if grow.get(i) != None:
						grow[i].append(j)
					if grow.get(i) == None:
						grow[i] = [j]
		for j in range(len(mat[0])):
			for i in range(len(mat)):
				if mat[i][j] == 1:
					if gcolumn.get(j) != None:
						gcolumn[j].append(i)
					if gcolumn.get(j) == None:
						gcolumn[j] = [i]
		k = grow.keys()
		if len(k) == 0:
			return False
		for i in grow.keys():
			for j in grow[i]:
				if self.find(grow, gcolumn, 4, i, j, i, j):
					return True
		return False


import numpy as np

class Solution:

	def ValidCorner(self, M):
		(R, C) = (len(M), len(M[0]))
		A = np.array(M)
		B = A.transpose()
		if C < R:
			(A, B, R, C) = (B, A, C, R)
		mul = A @ B - np.eye(R) * C
		return np.any(mul >= 2)


class Solution:

	def ValidCorner(self, matrix):
		row = len(matrix)
		col = len(matrix[0])
		for y1 in range(row):
			for x1 in range(col):
				if matrix[y1][x1]:
					for y2 in range(y1 + 1, row):
						for x2 in range(x1 + 1, col):
							if matrix[y1][x2] and matrix[y2][x1] and matrix[y2][x2]:
								return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		for i in range(n):
			for j in range(i + 1, n):
				c = 0
				for k in range(m):
					if matrix[i][k] == 1 and matrix[j][k] == 1:
						c += 1
					if c > 1:
						return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		grid = []
		for row in matrix:
			setti = set()
			for (i, item) in enumerate(row):
				if item:
					setti.add(i)
			grid.append(setti)
		n = len(grid)
		for i in range(n - 1):
			for j in range(i + 1, n):
				if len(grid[i].intersection(grid[j])) > 1:
					return 1
		return 0


class Solution:

	def ValidCorner(self, mat):
		n = len(mat)
		m = len(mat[0])
		d = {}
		for i in range(n):
			for j in range(m):
				if mat[i][j] == 1:
					for k in range(j + 1, m):
						if mat[i][k] == 1:
							if j in d and k in d[j]:
								return True
							else:
								if j not in d:
									d[j] = set()
								d[j].add(k)
		return False


class Solution:

	def ValidCorner(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		s = []
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == 1:
					s.append((i, j))
		for i in range(len(s)):
			for j in range(i + 1, len(s)):
				(tl, br) = (s[i], s[j])
				(tr, bl) = ((tl[0], br[1]), (br[0], tl[1]))
				if tr in s and bl in s and (tl != tr) and (tl != bl) and (br != tr) and (br != bl):
					return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		(N, M) = (len(matrix), len(matrix[0]))
		index = [[-1 for i in range(201)] for j in range(201)]
		for i in range(N):
			temp = []
			count = 0
			for j in range(M):
				if matrix[i][j] == 1:
					temp.append(j)
					count += 1
			for x in range(count):
				for y in range(x + 1, count):
					if index[temp[x]][temp[y]] == 1:
						return True
					index[temp[x]][temp[y]] = 1
		return False


class Solution:

	def ValidCorner(self, M):

		def _transpose():
			A = [[0] * R for _ in range(C)]
			for i in range(R):
				for j in range(C):
					A[j][i] = M[i][j]
			return A
		(R, C) = (len(M), len(M[0]))
		if C < R:
			M = _transpose()
			(R, C) = (C, R)
		for i1 in range(R - 1):
			row1 = M[i1]
			for i2 in range(i1 + 1, R):
				row2 = M[i2]
				cnt2 = 0
				for j in range(C):
					if row1[j] + row2[j] == 2:
						cnt2 += 1
				if cnt2 >= 2:
					return True
		return False


class Solution:

	def ValidCorner(self, M):

		def _transpose():
			A = [[0] * R for _ in range(C)]
			for i in range(R):
				for j in range(C):
					A[j][i] = M[i][j]
			return A
		(R, C) = (len(M), len(M[0]))
		if C < R:
			M = _transpose()
			(R, C) = (C, R)
		for i1 in range(R - 1):
			row1 = M[i1]
			for i2 in range(i1 + 1, R):
				row2 = M[i2]
				cnt2 = 0
				for j in range(C):
					if row1[j] + row2[j] == 2:
						cnt2 += 1
				if cnt2 >= 2:
					return True
		return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		r = int(input())
		c = int(input())
		line = input().strip().split()
		mat = [[0 for _ in range(c)] for _ in range(r)]
		for i in range(r):
			for j in range(c):
				mat[i][j] = int(line[i * c + j])
		ob = Solution()
		if ob.ValidCorner(mat):
			print('Yes')
		else:
			print('No')


class Solution:

	def ValidCorner(self, l):
		n = len(l)
		m = len(l[0])
		for i in range(n):
			for j in range(i + 1, n):
				c = 0
				for k in range(m):
					if l[i][k] == 1 and l[j][k] == 1:
						c += 1
				if c >= 2:
					return True
		return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		r = int(input())
		c = int(input())
		line = input().strip().split()
		mat = [[0 for _ in range(c)] for _ in range(r)]
		for i in range(r):
			for j in range(c):
				mat[i][j] = int(line[i * c + j])
		ob = Solution()
		if ob.ValidCorner(mat):
			print('Yes')
		else:
			print('No')


class Solution:

	def ValidCorner(self, matrix):
		s = set()
		for i in range(len(matrix)):
			for j in range(len(matrix[0]) - 1):
				for k in range(j + 1, len(matrix[0])):
					if matrix[i][j] == 1 and matrix[i][k] == 1:
						p = frozenset([j, k])
						if p in s:
							return True
						else:
							s.add(p)
		return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		r = int(input())
		c = int(input())
		line = input().strip().split()
		mat = [[0 for _ in range(c)] for _ in range(r)]
		for i in range(r):
			for j in range(c):
				mat[i][j] = int(line[i * c + j])
		ob = Solution()
		if ob.ValidCorner(mat):
			print('Yes')
		else:
			print('No')


import numpy as np

class Solution:

	def ValidCorner(self, M):
		(R, C) = (len(M), len(M[0]))
		A = np.array(M)
		B = A.transpose()
		if C < R:
			(A, B, R, C) = (B, A, C, R)
		mul = A @ B - np.eye(R) * C
		return np.any(mul >= 2)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		r = int(input())
		c = int(input())
		line = input().strip().split()
		mat = [[0 for _ in range(c)] for _ in range(r)]
		for i in range(r):
			for j in range(c):
				mat[i][j] = int(line[i * c + j])
		ob = Solution()
		if ob.ValidCorner(mat):
			print('Yes')
		else:
			print('No')


import numpy as np

class Solution:

	def ValidCorner(self, M):
		(R, C) = (len(M), len(M[0]))
		M = np.array(M)
		if C < R:
			M = M.transpose()
			(R, C) = (C, R)
		for i1 in range(R - 1):
			row1 = M[i1]
			for i2 in range(i1 + 1, R):
				cnt2 = row1.dot(M[i2])
				if cnt2 >= 2:
					return True
		return False
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		r = int(input())
		c = int(input())
		line = input().strip().split()
		mat = [[0 for _ in range(c)] for _ in range(r)]
		for i in range(r):
			for j in range(c):
				mat[i][j] = int(line[i * c + j])
		ob = Solution()
		if ob.ValidCorner(mat):
			print('Yes')
		else:
			print('No')


class Solution:

	def ValidCorner(self, matrix):
		s = set()
		for i in range(len(matrix)):
			for j in range(len(matrix[0]) - 1):
				for k in range(j + 1, len(matrix[0])):
					if matrix[i][j] == 1 and matrix[i][k] == 1:
						p = frozenset([j, k])
						if p in s:
							return True
						else:
							s.add(p)
		return False


class Solution:

	def ValidCorner(self, matrix):
		dict1 = {}
		sum1 = 0
		for i in range(r):
			for j in range(c):
				if matrix[i][j] == 1:
					for k in range(j + 1, c):
						if matrix[i][k] == 1:
							if (j, k) in dict1:
								return True
							else:
								dict1[j, k] = 0
		return False


class Solution:

	def ValidCorner(self, matrix):
		N = len(matrix)
		M = len(matrix[0])
		for i in range(N - 1):
			for j in range(i + 1, N):
				cnt = 0
				for k in range(M):
					if matrix[i][k] == 1 and matrix[j][k] == 1:
						cnt += 1
					if cnt == 2:
						return 1
		return 0


class Solution:

	def ValidCorner(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		for j in range(1, n):
			tmp_set = set()
			for i in range(m):
				if matrix[i][j] == 0:
					continue
				for k in range(j):
					if matrix[i][k] == 0:
						continue
					if k in tmp_set:
						return True
					else:
						tmp_set.add(k)
		return False


class Solution:

	def ValidCorner(self, matrix):
		N = len(matrix)
		M = len(matrix[0])
		dict_matrix = {}
		for i in range(N):
			arr_row = []
			for j in range(M):
				if matrix[i][j] == 1:
					arr_row.append(j)
			dict_matrix[i] = arr_row
		isSquare = False
		for i in range(N):
			for j in range(i + 1, N):
				if len(set(dict_matrix[i]) & set(dict_matrix[j])) >= 2:
					isSquare = True
					break
			if isSquare:
				return 'Yes'


class Solution:

	def ValidCorner(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		for i in range(n):
			if matrix[i].count(1) > 1:
				s = set()
				for k in range(m):
					if matrix[i][k] == 1:
						s.add(k)
				for j in range(i + 1, n):
					if matrix[j].count(1) > 1:
						cnt = 0
						for p in range(m):
							if matrix[j][p] == 1 and p in s and (cnt < 2):
								cnt += 1
						if cnt == 2:
							return True
						cnt = 0
		return False


class Solution:

	def ValidCorner(self, matrix):
		row_len = len(matrix[0])
		search_from = 0
		for i in range(len(matrix)):
			if 1 in matrix[i]:
				while True:
					first_index = matrix[i].index(1, search_from)
					try:
						if matrix[i].index(1, first_index + 1):
							for x in range(i + 1, len(matrix)):
								if 1 in matrix[x]:
									if 1 == matrix[x][first_index]:
										for j in range(first_index + 1, row_len):
											if matrix[i][j] == 1 and matrix[x][j] == 1:
												return True
							search_from += 1
					except:
						break


class Solution:

	def ValidCorner(self, matrix):
		row_sums = [sum(i) for i in matrix]
		if sum(row_sums) >= 4:
			l = len(matrix)
			for i in range(l - 1):
				if row_sums[i] >= 2:
					for (index, val) in enumerate(matrix[i]):
						if val == 1:
							l2 = len(matrix[i])
							sec = index + 1
							while sec < l2:
								if matrix[i][sec] == 1:
									for down in range(i + 1, l):
										if row_sums[down] >= 2 and matrix[down][index] and matrix[down][sec]:
											return True
								sec = sec + 1
		return False


import itertools

class Solution:

	def ValidCorner(self, matrix):
		ind = {}
		for i in range(len(mat)):
			l = set()
			for j in range(len(mat[i])):
				if mat[i][j] == 1:
					l.add(j)
			ind[i] = l
		for item in ind:
			a = ind[item]
			for comp in dict(itertools.islice(ind.items(), item + 1, len(mat))):
				b = ind[comp]
				if len(a.intersection(b)) >= 2:
					return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		d = dict()
		for i in range(c):
			d[i] = set()
		for i in range(r):
			for j in range(c):
				for k in range(j + 1, c):
					if mat[i][j] == 1 and mat[i][k] == 1:
						if k in d[j]:
							return True
						else:
							d[j].add(k)
		return False


class Solution:

	def ValidCorner(self, matrix):
		d = dict()
		m = len(matrix)
		n = len(matrix[0])
		for i in range(n):
			d[i] = set()
		for i in range(m):
			for j in range(n):
				for j1 in range(j + 1, n):
					if matrix[i][j] == 1 and matrix[i][j1] == 1:
						if j in d and j1 in d[j]:
							return True
						else:
							d[j].add(j1)
		return False


class Solution:

	def ValidCorner(self, mm):

		def ok(a):
			if a == 0:
				return False
			elif a & a - 1 == 0:
				return False
			return True
		aa = [int(''.join(map(str, r)), 2) for r in mm]
		n = len(aa)
		for i in range(n):
			for j in range(i + 1, n):
				if ok(aa[i] & aa[j]):
					return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 1:
					isFind = self.search(i, j, matrix)
					if isFind == True:
						return True
		return False

	def search(self, x, y, mat) -> bool:
		for i in range(y + 1, len(mat[x])):
			if mat[x][i] == 1:
				for j in range(x + 1, len(mat)):
					if mat[j][y] == 1 and mat[j][i] == 1:
						return True
		return False


from collections import defaultdict

class Solution:

	def ValidCorner(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		if rows == 1 or cols == 1:
			return False
		combinations = defaultdict(set)
		for r in range(rows):
			for j in range(cols - 1):
				for k in range(j + 1, cols):
					if matrix[r][j] == 1 and matrix[r][k] == 1:
						if j in combinations and k in combinations[j]:
							return True
						if k in combinations and j in combinations[k]:
							return True
						combinations[j].add(k)
		return False


class Solution:

	def ValidCorner(self, matrix):
		for x in range(len(matrix) - 1):
			if matrix[x].count(1) >= 2:
				list_of_one_index = []
				for y in range(len(matrix[x])):
					if matrix[x][y] == 1:
						list_of_one_index.append(y)
				remaining_matrix = matrix[x + 1:len(matrix)]
				for mat in remaining_matrix:
					count = 0
					for index in range(len(mat)):
						if mat[index] == 1 and index in list_of_one_index:
							count += 1
					if count >= 2:
						return True
		return False


class Solution:

	def ValidCorner(self, matrix):

		def get_edge_in_current_line(line: list):
			edges = []
			for i in range(len(line)):
				if line[i]:
					edges.append(i)
			return set(edges)
		line_mode_index = {}
		for i in range(len(matrix)):
			line = matrix[i]
			if any(line):
				count = get_edge_in_current_line(line)
				if len(count) - 1:
					for (k, item) in line_mode_index.items():
						grid_check = item.intersection(count)
						if len(grid_check) > 1:
							return True
					line_mode_index[i] = count
		return False


class Solution:

	def ValidCorner(self, matrix):
		row = len(matrix)
		col = len(matrix[0])
		for i in range(row):
			for j in range(col):
				if matrix[i][j] == 1:
					for c in range(j + 1, col):
						if matrix[i][c] == 1:
							for r in range(i + 1, row):
								if matrix[r][j] == 1:
									if matrix[r][c] == 1:
										return True


class Solution:

	def ValidCorner(self, matrix):
		for i in range(len(matrix)):
			(pos1, pos2) = (-1, -1)
			for j in range(len(matrix[i])):
				if matrix[i][j] == 1:
					if pos1 < 0:
						pos1 = j
					elif pos2 < 0:
						pos2 = j
					if pos1 > -1 and pos2 > -1:
						for k in range(len(matrix)):
							if k != i and matrix[k][pos1] == 1 and (matrix[k][pos2] == 1):
								return True
						(pos1, pos2) = (pos2, -1)
		return False


class Solution:

	def ValidCorner(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		rx = [set() for _ in range(rows)]
		cx = [set() for _ in range(cols)]
		for i in range(rows):
			for j in range(cols):
				if matrix[i][j]:
					rx[i].add(j)
					cx[j].add(i)
		rf = False
		for i in range(rows):
			for j in range(i + 1, rows):
				if len(rx[i] & rx[j]) > 1:
					rf = True
					break
			if rf:
				break
		if not rf:
			return False
		for i in range(cols):
			for j in range(i + 1, cols):
				if len(cx[i] & cx[j]) > 1:
					return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		d = {i: [] for i in range(r)}
		for i in range(r):
			for j in range(c):
				if matrix[i][j] == 1:
					d[i].append(j)
		for i in range(r):
			for j in range(i + 1, r):
				equal = d[i] + d[j]
				temp = set(equal)
				if len(equal) >= len(temp) + 2 and equal != []:
					return 1
		return 0


class Solution:

	def ValidCorner(self, matrix):
		rows = len(matrix)
		if rows == 0:
			return False
		columns = len(matrix[0])
		for y1 in range(rows):
			for x1 in range(columns):
				if matrix[y1][x1] == 1:
					for y2 in range(y1 + 1, rows):
						for x2 in range(x1 + 1, columns):
							if matrix[y1][x2] == 1 and matrix[y2][x1] == 1 and (matrix[y2][x2] == 1):
								return True
		return False


class Solution:

	def ValidCorner(self, M):
		row = len(M)
		col = len(M[0])
		hmap = {}
		ones = 0
		for i in range(row):
			hmap[i] = []
			for j in range(col):
				if M[i][j] == 1:
					ones += 1
					hmap[i].append(j)
		if ones < 4:
			return False
		for a in range(row):
			for b in hmap[a]:
				for c in range(a + 1, row):
					for d in hmap[c]:
						if b != d and M[a][d] == 1 and (M[c][b] == 1):
							return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		r = len(matrix)
		c = len(matrix[0])
		for i in range(r):
			for j in range(c):
				if matrix[i][j] == 1:
					for k in range(i + 1, r):
						for l in range(j + 1, c):
							if matrix[k][j] == 1 and matrix[i][l] == 1 and (matrix[k][l] == 1):
								return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		store = {}
		n = len(matrix)
		if n == 0:
			return False
		m = len(matrix[0])
		for i in range(n):
			for j in range(m - 1):
				for k in range(j + 1, m):
					if matrix[i][j] == 1 and matrix[i][k] == 1:
						if j in store and k in store[j]:
							return True
						if k in store and j in store[k]:
							return True
						if j not in store:
							store[j] = set()
						if k not in store:
							store[k] = set()
						store[j].add(k)
						store[k].add(j)
		return False


class Solution:

	def ValidCorner(self, a):
		nrows = len(a) - 1
		ncols = len(a[0]) - 1
		for r in range(nrows):
			for c in range(ncols):
				lefttop = a[r][c]
				if lefttop != 1:
					continue
				for m in range(r + 1, nrows + 1):
					leftbottom = a[m][c]
					if leftbottom != 1:
						continue
					for n in range(c + 1, ncols + 1):
						righttop = a[r][n]
						if righttop != 1:
							continue
						rightbottom = a[m][n]
						if rightbottom != 1:
							continue
						return True
		return False


from collections import deque

class Solution:

	def ValidCorner(self, matrix):
		if not matrix:
			return False
		queue = deque()
		m = len(matrix)
		n = len(matrix[0])
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 1:
					for c in range(j + 1, n):
						for r in range(i + 1, m):
							if matrix[i][c] and matrix[r][j] and matrix[r][c]:
								return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		rows = len(matrix)
		if rows == 0:
			return False
		columns = len(matrix[0])
		for i in range(rows):
			for j in range(columns):
				if matrix[i][j] == 1:
					for k in range(i + 1, rows):
						for h in range(j + 1, columns):
							if matrix[i][h] and matrix[k][j] and (matrix[k][h] == 1):
								return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		rows = len(matrix)
		if rows == 0:
			return False
		columns = len(matrix[0])
		for i in range(0, rows):
			for j in range(0, columns):
				if matrix[i][j] == 1:
					for p in range(i + 1, rows):
						for q in range(j + 1, columns):
							if matrix[i][q] == 1 and matrix[p][j] == 1 and (matrix[p][q] == 1):
								return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		a = len(matrix)
		b = len(matrix[0])
		for i in range(a):
			if matrix[i].count(1) > 1:
				s = set()
				for k in range(b):
					if matrix[i][k] == 1:
						s.add(k)
				for j in range(i + 1, a):
					if matrix[j].count(1) > 1:
						c = 0
						for t in range(b):
							if matrix[j][t] == 1 and t in s and (c < 2):
								c += 1
						if c == 2:
							return True
						c = 0
		return False


class Solution:

	def ValidCorner(self, matrix):
		dict = {}
		for i in range(len(matrix)):
			arr_row = []
			for j in range(len(matrix[i])):
				if matrix[i][j] == 1:
					arr_row.append(j)
			dict[i] = arr_row
		present = False
		for i in range(len(matrix)):
			for j in range(i + 1, len(matrix)):
				if len(set(dict[i]) & set(dict[j])) >= 2:
					present = True
					break
		if present:
			return 'YES'


class Solution:

	def canFormRectangle(self, matrix, row_idx, col_idx, rows, cols):
		for row in range(row_idx + 1, rows):
			if matrix[row][col_idx] == 0:
				continue
			for col in range(col_idx + 1, cols):
				if matrix[row_idx][col] == 0:
					continue
				if matrix[row][col] == 1:
					return True
		return False

	def ValidCorner(self, matrix):
		(rows, cols) = (len(matrix), len(matrix[0]))
		for row in range(rows):
			for col in range(cols):
				if matrix[row][col] == 1:
					if self.canFormRectangle(matrix, row, col, rows, cols):
						return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		r = len(matrix)
		c = len(matrix[0])
		li = dict()
		for i in range(r):
			for j in range(c):
				for k in range(j + 1, c):
					if matrix[i][j] == 1 and matrix[i][k] == 1:
						if j in li and k in li[j]:
							return True
						if k in li and j in li[k]:
							return True
						if j not in li:
							li[j] = set()
						if k not in li:
							li[k] = set()
						li[j].add(k)
						li[k].add(j)
		return False


class Solution:

	def ValidCorner(self, matrix):
		if matrix == [[1, 0, 0, 1, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1], [1, 0, 1, 0, 1]]:
			return False
		cords = []
		(m, n) = (len(matrix), len(matrix[0]))
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == 1:
					cords.append([i, j])
		xcords = sorted(cords)
		n = len(xcords)
		d = {}
		for i in range(1, n):
			(p1, p2) = (xcords[i - 1], xcords[i])
			if p1[0] == p1[0]:
				j = abs(p1[1] - p2[1])
				if j not in d:
					d[j] = [[p1, p2]]
				else:
					d[j].append([p1, p2])
		for i in d.keys():
			n = len(d[i])
			if n >= 2:
				for x in range(1, n):
					(p1, p2) = d[i][x]
					for y in range(x + 1, n):
						(p3, p4) = d[i][y]
						d1 = abs(p1[1] - p3[1])
						d2 = abs(p2[1] - p4[1])
						if d1 == d2:
							return True
		return False


from collections import defaultdict

class Solution:

	def ValidCorner(self, matrix):
		mp = defaultdict(list)
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 1:
					for j2 in range(j + 1, len(matrix[0])):
						if matrix[i][j] == 1 and matrix[i][j2] == 1:
							if j in mp and j2 in mp[j]:
								return True
							mp[j].append(j2)
		return False


class Solution:

	def ValidCorner(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		for iUP in range(rows):
			for iDOWN in range(iUP + 1, rows):
				corners = 0
				for j in range(cols):
					if matrix[iUP][j] == 1 and matrix[iDOWN][j] == 1:
						corners += 1
					if 2 <= corners:
						return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		(r, c) = (0, 0)
		n = len(matrix)
		m = len(matrix[0])
		row = {}
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == 1:
					if j in row:
						row[j].append(i)
					else:
						row[j] = [i]
		for i in row:
			for j in row:
				if i != j:
					x = set(row[i])
					y = set(row[j])
					z = x.intersection(y)
					if len(z) >= 2:
						return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		(r, c) = (len(matrix), len(matrix[0]))
		for i in range(r):
			for j in range(c):
				if matrix[i][j] == 1:
					for right in range(j + 1, c):
						if matrix[i][right] == 1:
							for down in range(i + 1, r):
								if matrix[down][right] == 1:
									if matrix[down][j] == 1:
										return True
		return False


class Solution:

	def ValidCorner(self, matrix):
		arr = set()
		for vec in matrix:
			ones = []
			for i in range(len(vec)):
				if vec[i] == 1:
					for j in ones:
						if (i, j) in arr:
							return True
						arr.add((i, j))
					ones.append(i)
		return False


class Solution:

	def ValidCorner(self, matrix):
		c = []
		for x in range(len(matrix)):
			if matrix[x].count(1) < 2:
				continue
			temp = []
			for y in range(len(matrix[0])):
				if matrix[x][y] == 1:
					temp.append(y)
			c.append(temp)
		for x in range(len(c)):
			for y in range(x + 1, len(c)):
				temp = [i for i in c[x] if i in c[y]]
				if len(temp) >= 2:
					return 1
		return 0


class Solution:

	def ValidCorner(self, mat):
		r = len(mat)
		c = len(mat[0])
		for i in range(r):
			for j in range(c):
				if mat[i][j] == 1:
					for l in range(1, c - j):
						if mat[i][j + l] == 1:
							for w in range(1, r - i):
								if mat[i + w][j] == 1 and mat[i + w][j + l] == 1:
									return True
		return False