Given a boolean matrix of size RxC where each cell contains either 0 or 1, find the row numbers of row (0-based) which already exists or are repeated.
Example 1:
Input:
R = 2, C = 2
matrix[][] = {{1, 0},
              {1, 0}}
Output: 
1
Explanation:
Row 1 is duplicate of Row 0.
Example 2:
Input:
R = 4, C = 3
matrix[][] = {{ 1, 0, 0},
              { 1, 0, 0},
              { 1, 0, 0},
              { 0, 0, 0}}
Output: 
1 2 
Explanation:
Row 1 and Row 2 are duplicates of Row 0. 
Your Task:
You dont need to read input or print anything. Complete the function repeatedRows() that takes the matrix as input parameter and returns a list of row numbers which are duplicate rows.
 
Expected Time Complexity: O(R * C)
Expected Auxiliary Space: O(R*C) 
 
Constraints:
1 ≤ R ≤ 1000
1 ≤ C ≤ 20
0 ≤ matrix[i][j] ≤ 1

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Matrices

Data structures

String algorithms

Starter code: #User function Template for python3

class Solution:
    def repeatedRows(self, arr, m ,n):
        #code here

Solutions:
class Solution:

	def repeatedRows(self, arr, m, n):
		d = dict()
		z = []
		for i in range(m):
			d[tuple(arr[i])] = 0
		for i in range(m):
			d[tuple(arr[i])] = d[tuple(arr[i])] + 1
			if d[tuple(arr[i])] > 1:
				z.append(i)
		return z


class Solution:

	def repeatedRows(self, arr, m, n):
		l = []
		c = 0
		res = []
		for i in range(0, m):
			if arr[i] not in l:
				l.append(arr[i])
			else:
				res.append(i)
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		l = {}
		ans = []
		for i in range(len(arr)):
			t = tuple(arr[i])
			if t in l:
				ans.append(i)
			else:
				l[t] = 1
		return ans


class Solution:

	def repeatedRows(self, arr, n, m):
		dic = {}
		res = []
		for i in range(n):
			st = ''
			for j in range(m):
				st += str(arr[i][j])
			if st not in dic:
				dic[st] = []
			else:
				dic[st].append(i)
				res.append(i)
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		ans = []
		dct = dict()
		for i in range(m):
			if tuple(arr[i]) in dct:
				ans.append(i)
			else:
				dct[tuple(arr[i])] = 1
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		e = []
		s = []
		for i in arr:
			if i not in s:
				s.append(i)
		d = {}
		for i in range(len(arr)):
			ind = s.index(arr[i])
			if ind not in d:
				d[ind] = [i]
			else:
				d[ind] += [i]
		for i in d.values():
			if len(i) > 1:
				e += i[1:]
		e.sort()
		return e


class Solution:

	def repeatedRows(self, arr, m, n):
		d = {}
		ans = []
		for i in range(m):
			temp = tuple(arr[i])
			if temp in d:
				ans.append(i)
			else:
				d[temp] = 1
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		l = []
		l1 = []
		for i in range(m):
			if arr[i] in l1:
				l.append(i)
			else:
				l1.append(arr[i])
		return l


class Solution:

	def repeatedRows(self, arr, m, n):
		nt = {}
		ans = []
		idx = 0
		for i in arr:
			k = str(i)
			if k in nt:
				ans.append(idx)
			else:
				nt[k] = 1
			idx += 1
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		mp = {}
		t = []
		for i in range(m):
			if tuple(arr[i]) not in mp:
				mp[tuple(arr[i])] = 1
			else:
				t.append(i)
		return t


class Solution:

	def repeatedRows(self, a, m, n):
		d = {}
		for i in range(m):
			l = []
			for j in range(n):
				l.append(a[i][j])
			binary = ''.join([str(i) for i in l])
			num = int(binary, 2)
			d[i] = num
		list = []
		ans = []
		for (i, j) in d.items():
			if j not in list:
				list.append(j)
			else:
				ans.append(i)
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		temp = []
		ans = []
		for i in range(m):
			s = ''
			for j in range(n):
				s += str(arr[i][j])
			if s in temp:
				ans.append(i)
			else:
				temp.append(s)
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		map = {}
		ans = []
		for r in range(m):
			dec = 0
			for c in range(n):
				dec += arr[r][c] * 10 ** c
			if dec not in map:
				map[dec] = True
			else:
				ans.append(r)
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		l = set()
		for i in range(m):
			for j in range(i + 1, m):
				if arr[i] == arr[j]:
					l.add(j)
		return sorted(l)


class Solution:

	def repeatedRows(self, arr, m, n):
		ans = []
		d = {}
		for i in range(m):
			deci = 0
			for j in range(n):
				deci += arr[i][j] * pow(2, j)
			if deci in d:
				ans.append(i)
			d[deci] = i
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		setti = set()
		output = []
		for i in range(m):
			if tuple(arr[i]) in setti:
				output.append(i)
			else:
				setti.add(tuple(arr[i]))
		return output


from collections import defaultdict

class Solution:

	def fun(self):
		return -1

	def repeatedRows(self, arr, m, n):
		res = []
		d = defaultdict(self.fun)
		for i in range(m):
			if d[tuple(arr[i])] != -1:
				res.append(i)
			else:
				d[tuple(arr[i])] = 1
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		s = set()
		ans = []
		for (i, j) in enumerate(arr):
			t = ''.join(map(str, j))
			if t in s:
				ans.append(i)
			else:
				s.add(t)
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		d = {}
		i = []
		c = 0
		for x in arr:
			if d.get(str(x)) == None:
				d[str(x)] = 0
			else:
				i.append(c)
			c += 1
		return i


class Solution:

	def repeatedRows(self, arr, m, n):
		d = dict()
		ans = []
		for x in range(m):
			p = str(arr[x])
			if d.get(p) != None:
				ans.append(x)
			d[p] = True
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		store = set()
		ans = []
		ind = 0
		for a in arr:
			c = 0
			for i in range(len(a)):
				c += (1 << i) * a[i]
			if c in store:
				ans.append(ind)
			ind += 1
			store.add(c)
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		l = []
		a = []
		for i in range(len(arr)):
			if arr[i] not in l:
				l.append(arr[i])
			else:
				a.append(i)
		return a


class Solution:

	def repeatedRows(self, arr, m, n):
		d = {}
		ans = []
		ind = 0
		for i in arr:
			t = ''
			for j in i:
				t += str(j)
			if t not in d:
				d[t] = arr
			else:
				ans.append(ind)
			ind += 1
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		freq = {}
		res = []
		for i in range(len(arr)):
			if tuple(arr[i]) in freq:
				res.append(i)
			else:
				freq[tuple(arr[i])] = 1
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		unique = []
		res = []
		for i in range(len(arr)):
			if arr[i] not in unique:
				unique.append(arr[i])
			else:
				res.append(i)
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		d = {}
		ans = []
		for (j, row) in enumerate(arr):
			curr = ''
			for i in row:
				curr += str(i)
			if curr not in d:
				d[curr] = True
			else:
				ans.append(j)
		return ans


class Node:

	def __init__(self):
		self.children = [None] * 2
		self.flag = False

class Trie:

	def __init__(self):
		self.root = self.getNode()

	def getNode(self):
		return Node()

	def insert(self, key):
		size = len(key)
		node = self.root
		for i in range(size):
			if node.children[key[i]] == None:
				node.children[key[i]] = self.getNode()
			node = node.children[key[i]]
		if node.flag:
			return True
		else:
			node.flag = True
			return False

class Solution:

	def repeatedRows(self, arr, m, n):
		result = []
		t = Trie()
		for i in range(m):
			res = t.insert(arr[i])
			if res:
				result.append(i)
		return result


class Node:

	def __init__(self):
		self.children = {}
		self.finish = False

class Solution:

	def __init__(self):
		self.root = Node()

	def addData(self, root, data, index, result):
		for i in data:
			if i not in root.children:
				root.children[i] = Node()
			root = root.children[i]
		if root.finish == True:
			result.append(index)
		root.finish = True

	def repeatedRows(self, arr, m, n):
		result = []
		root = self.root
		for i in range(len(arr)):
			self.addData(root, arr[i], i, result)
		return result


class Solution:

	def repeatedRows(self, arr, m, n):
		d = {}
		ls = []
		count = 0
		for i in arr:
			s = ''.join((str(x) for x in i))
			if s in d:
				ls.append(count)
				count += 1
			else:
				d[s] = 1
				count += 1
		return ls


class Solution:

	def repeatedRows(self, arr, m, n):

		class TrieNode:

			def __init__(self):
				self.child = {}
				self.Eow = False

		def insert_check(i, Trie):
			for c in range(n):
				if arr[i][c] not in Trie.child:
					Trie.child[arr[i][c]] = TrieNode()
				Trie = Trie.child[arr[i][c]]
			if not Trie.Eow:
				Trie.Eow = True
			else:
				res.append(i)
		Trie = TrieNode()
		res = []
		for r in range(m):
			insert_check(r, Trie)
		return res


class TrieNode:

	def __init__(self):
		self.links = [None] * 2

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		flag = 1
		curr = self.root
		for ele in key:
			if not curr.links[ord(ele) - ord('a')]:
				curr.links[ord(ele) - ord('a')] = TrieNode()
				flag = 0
			curr = curr.links[ord(ele) - ord('a')]
		return flag

	def search(self, key):
		curr = self.root
		for ele in key:
			if not curr.links[ord(ele) - ord('a')]:
				return False
			curr = curr.links[ord(ele) - ord('a')]
		return True

class Solution:

	def repeatedRows(self, arr, m, n):
		t = Trie()
		ans = []
		for i in range(m):
			temp = ''
			for j in range(n):
				if arr[i][j]:
					temp += 'a'
				else:
					temp += 'b'
			if t.insert(temp):
				ans += [i]
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		d = []
		ans = []
		for i in range(len(arr)):
			if arr.count(arr[i]) > 1:
				d.append(arr[i])
		for i in range(0, len(arr)):
			if arr[i] in d and i != arr.index(arr[i]):
				ans.append(i)
		return ans


class Node:

	def __init__(self):
		self.link = dict()

class Trie:

	def __init__(self):
		self.root = Node()

	def insert(self, row):
		tem = self.root
		for i in row:
			if i not in tem.link:
				tem.link[i] = Node()
			tem = tem.link[i]

	def search(self, row):
		tem = self.root
		for i in row:
			if i not in tem.link:
				return False
			tem = tem.link[i]
		return True

class Solution:

	def repeatedRows(self, arr, m, n):
		tri = Trie()
		answer = []
		for i in range(m):
			if tri.search(arr[i]):
				answer.append(i)
			else:
				tri.insert(arr[i])
		return answer


class Solution:

	def repeatedRows(self, arr, m, n):
		unique = set()
		ans = []
		for (i, row) in enumerate(map(tuple, arr)):
			if row not in unique:
				unique.add(row)
			else:
				ans.append(i)
		return ans


class Trie:

	def __init__(self):
		self.children = {}
		self.eow = False

class Solution:

	def create(self, row):
		cur = self.root
		for num in row:
			if num not in cur.children:
				cur.children[num] = Trie()
			cur = cur.children[num]
		if cur.eow == True:
			return -1
		cur.eow = True
		return 1

	def repeatedRows(self, arr, m, n):
		self.root = Trie()
		res = []
		for (ind, row) in enumerate(arr):
			flag = self.create(row)
			if flag == -1:
				res.append(ind)
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		st = set()
		ans = []
		for i in range(m):
			s = ''
			for j in range(n):
				s += str(arr[i][j])
			if s in st:
				ans.append(i)
			else:
				st.add(s)
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		s = set()
		ans = []
		for i in range(m):
			temp = 0
			for j in range(n - 1, -1, -1):
				temp += arr[i][j] * (1 << j)
			if temp in s:
				ans.append(i)
			s.add(temp)
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		d = {}
		ans = []
		for i in range(m):
			if '-'.join([str(i) for i in arr[i]]) in d:
				ans.append(i)
			else:
				d['-'.join([str(i) for i in arr[i]])] = 1
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		mp = {}
		ans = []
		p = 0
		for i in arr:
			k = str(i)
			if k in mp:
				ans.append(p)
			else:
				mp[k] = 1
			p += 1
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		l = []
		s = {}
		c = 0
		for i in arr:
			t = ''.join(i)
			if t in s:
				l.append(c)
			else:
				s[t] = 1
			c += 1
		return l


class Solution:

	def repeatedRows(self, arr, m, n):
		ar = []
		for i in range(m):
			for j in range(i + 1, m):
				if arr[i] == arr[j] and j not in ar:
					ar.append(j)
		ar.sort()
		return ar


class Solution:

	def repeatedRows(self, arr, m, n):
		rowmap = {}
		ans = []
		for row in range(m):
			key = ''
			for col in arr[row]:
				key += str(col)
			if rowmap.get(key, -1) != -1:
				ans.append(row)
			else:
				rowmap[key] = 1
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		new = []
		ans = []
		for i in range(len(arr)):
			a = arr[i]
			if a in new:
				ans.append(i)
			else:
				new.append(a)
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = list(map(int, input().strip().split()))
		arr = []
		for i in range(n):
			nums = list(map(int, input().strip().split()))
			arr.append(nums)
		ob = Solution()
		ans = ob.repeatedRows(arr, n, m)
		for x in ans:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def repeatedRows(self, arr, m, n):
		rowmap = {}
		ans = []
		for row in range(m):
			key = ''
			for col in arr[row]:
				key += str(col)
			if rowmap.get(key, -1) != -1:
				ans.append(row)
			else:
				rowmap[key] = 1
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = list(map(int, input().strip().split()))
		arr = []
		for i in range(n):
			nums = list(map(int, input().strip().split()))
			arr.append(nums)
		ob = Solution()
		ans = ob.repeatedRows(arr, n, m)
		for x in ans:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def repeatedRows(self, arr, m, n):
		x = set()
		for i in range(len(arr)):
			for j in range(len(arr[i])):
				arr[i][j] = str(arr[i][j])
		ans = []
		for i in range(len(arr)):
			s = ''.join(arr[i])
			if s in x:
				ans.append(i)
			else:
				x.add(s)
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = list(map(int, input().strip().split()))
		arr = []
		for i in range(n):
			nums = list(map(int, input().strip().split()))
			arr.append(nums)
		ob = Solution()
		ans = ob.repeatedRows(arr, n, m)
		for x in ans:
			print(x, end=' ')
		print()
		tc -= 1


class Solution:

	def repeatedRows(self, arr, m, n):
		new = []
		ans = []
		for i in range(len(arr)):
			x = arr[i]
			if x in new:
				ans.append(i)
			else:
				new.append(x)
		return ans


class Trie:

	def __init__(self):
		self.arr = [None, None]

	def insert(self, a, n, root):
		f = True
		for i in range(len(a)):
			if root.arr[a[i]] == None:
				f = False
				root.arr[a[i]] = Trie()
			root = root.arr[a[i]]
		return f

class Solution:

	def repeatedRows(self, arr, m, n):
		a = []
		root = Trie()
		for i in range(m):
			if root.insert(arr[i], n, root):
				a.append(i)
		return a


class Solution:

	def repeatedRows(self, arr, m, n):
		rowmap = {}
		ans = []
		for row in range(m):
			key = ''
			for col in arr[row]:
				key += str(col)
			if rowmap.get(key, -1) != -1:
				ans.append(row)
			else:
				rowmap[key] = 1
		return ans
		mat = arr
		arr1 = [[-124] * n] * m
		ans = []
		arr1[0] = mat[0]
		for i in range(1, len(mat)):
			if mat[i] in arr1:
				ans.append(i)
				arr1[i] = mat[i]
			else:
				arr[i] = mat[i]
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		l = []
		for i in range(m):
			s = ''
			for j in range(n):
				s += str(arr[i][j])
			l.append(s)
		res = []
		for i in range(1, m):
			for j in range(i):
				if l[i] == l[j]:
					res.append(i)
					break
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		dec = {}
		ans = []
		for i in range(m):
			count = 0
			multiplyer = 1
			for j in range(n):
				count += arr[i][j] * multiplyer
				multiplyer <<= 1
			if dec.get(count):
				ans.append(i)
			else:
				dec[count] = 1
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		m1 = {}
		c = []
		for i in range(m):
			z = tuple(arr[i])
			if z in m1:
				c.append(i)
			else:
				m1[z] = 1
		return c


class TrieNode:

	def __init__(self):
		self.children = dict()
		self.isLeaf = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def insert(self, key):
		present = True
		current = self.root
		for char in key:
			if char not in current.children:
				present = False
				current.children[char] = TrieNode()
			current = current.children[char]
		return present

class Solution:

	def repeatedRows(self, arr, m, n):
		repeated = []
		trie = Trie()
		for i in range(m):
			temp = ''
			for j in range(n):
				temp += str(arr[i][j])
			if trie.insert(temp):
				repeated.append(i)
		return repeated


class Solution:

	def repeatedRows(self, l, n, m):
		s = set()
		ans = []
		for i in range(n):
			t = 0
			for j in range(m):
				t += l[i][j] * 2 ** (m - j)
			if t in s:
				ans.append(i)
			else:
				s.add(t)
		return ans


class Solution:

	def repeatedRows(self, arr, n, m):
		d = set()
		ans = []
		for i in range(n):
			t = ()
			for j in range(m):
				t += (arr[i][j],)
			if t in d:
				ans.append(i)
			else:
				d.add(t)
		return ans


class Solution:

	def repeatedRows(self, arr, m, n):
		ansarr = []
		s = set()
		for i in range(m):
			string = ''
			for j in range(n):
				string += str(arr[i][j])
			if string in s:
				ansarr.append(i)
			else:
				s.add(string)
		return ansarr


class Solution:

	def repeatedRows(self, arr, m, n):
		s = set()
		a = []
		c = 0
		for i in arr:
			st = ''
			for j in i:
				st = st + str(j)
			if st in s:
				a.append(c)
			else:
				s.add(st)
			c += 1
		return a


class Solution:

	def repeatedRows(self, arr, m, n):
		st = set()
		res = []
		for (i, lst) in enumerate(arr):
			st_lst = str(lst)
			if st_lst in st:
				res.append(i)
			else:
				st.add(st_lst)
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		l = []
		r = [-1 for i in range(pow(2, n))]
		for i in range(m):
			no = 0
			k = 0
			for j in range(n - 1, -1, -1):
				no += arr[i][j] * pow(2, k)
				k += 1
			if r[no] == -1:
				r[no] = i
			else:
				l.append(i)
		return l


class TrieNode:

	def __init__(self):
		self.children = {}
		self.end = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def search(self, arr):
		temp = self.root
		for i in range(len(arr)):
			if arr[i] not in temp.children:
				return False
			temp = temp.children[arr[i]]
		return temp.end

	def insert(self, arr):
		temp = self.root
		for i in range(len(arr)):
			if arr[i] not in temp.children:
				temp.children[arr[i]] = TrieNode()
			temp = temp.children[arr[i]]
		temp.end = True

class Solution:

	def repeatedRows(self, arr, m, n):
		strings = set()
		res = []
		for r in range(m):
			s = ''
			for c in range(n):
				s += str(arr[r][c])
			if s in strings:
				res.append(r)
			else:
				strings.add(s)
		return res


class TrieNode:

	def __init__(self):
		self.children = {}
		self.end = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def search(self, arr):
		temp = self.root
		for i in range(len(arr)):
			if arr[i] not in temp.children:
				return False
			temp = temp.children[arr[i]]
		return temp.end

	def insert(self, arr):
		temp = self.root
		for i in range(len(arr)):
			if arr[i] not in temp.children:
				temp.children[arr[i]] = TrieNode()
			temp = temp.children[arr[i]]
		temp.end = True

class Solution:

	def repeatedRows(self, arr, m, n):
		res = []
		obj = Trie()
		for i in range(m):
			if not obj.search(arr[i]):
				obj.insert(arr[i])
			else:
				res.append(i)
		return res


class TrieNode:

	def __init__(self):
		self.children = {}
		self.rowEnd = False

class Trie:

	def __init__(self):
		self.root = TrieNode()

	def search(self, row):
		temp = self.root
		for r in row:
			if r not in temp.children:
				return False
			temp = temp.children[r]
		return temp.rowEnd

	def insert(self, row):
		temp = self.root
		for r in row:
			if r not in temp.children:
				temp.children[r] = TrieNode()
			temp = temp.children[r]
		temp.rowEnd = True

class Solution:

	def repeatedRows(self, arr, m, n):
		(res, _trie) = ([], Trie())
		ROWS = len(arr)
		_trie.insert(arr[0])
		for i in range(1, ROWS):
			if _trie.search(arr[i]):
				res.append(i)
			else:
				_trie.insert(arr[i])
		return res


class Solution:

	def repeatedRows(self, arr, m, n):
		strings = set()
		res = []
		for r in range(m):
			s = ''
			for c in range(n):
				s += str(arr[r][c])
			if s in strings:
				res.append(r)
			else:
				strings.add(s)
		return res


class trie:

	def __init__(self):
		self.child = [-1] * 2
		self.end = False

class Solution:

	def repeatedRows(self, arr, m, n):
		root = trie()
		ans = []
		for i in range(m):
			curr = root
			for j in range(n):
				bol = arr[i][j]
				if curr.child[bol] == -1:
					curr.child[bol] = trie()
				curr = curr.child[bol]
			if curr.end == False:
				curr.end = True
			else:
				ans.append(i)
		return ans