[LeetCode] 2965. Find Missing and Repeated Values (Python)

Problem

 

Solution

array

n*n 2차 배열에서 중복된 값, 존재하지 않는 값을 찾는 문제.

hash를 사용해서 frequency를 구한다음에 정답을 구해도되고

나는  1~n*n까지 연속된 숫자이므로 visited 를 사용해서 이미 방문했는지를 체크하도록 했다.

 

 

Code

class Solution:
    def findMissingAndRepeatedValues(self, grid: List[List[int]]) -> List[int]:
        answer = []
        n = len(grid)
        visited = [0] * (n*n + 1)
        twice_num = 0
        missing_num = 0
        
        for i in range(n):
            for j in range(n):
                current_val = grid[i][j]
                if  visited[current_val] == 1:
                    twice_num = current_val
                else:
                    visited[current_val] = 1
        
        for i in range(1, len(visited)):
            if visited[i] == 0:
                missing_num = i
        answer = [twice_num, missing_num]
        return answer

 

Complexity

Time Complexity

2중 for문을 순회하므로 O(N^2)

 

Space Complexity

visited 리스트가 O(n^2)을 차지하는 가장 큰 공간이므로,
최종적으로 공간 복잡도는 O(n^2)이다.