[LC] 1901. Find a Peak Element II

[seungriyou]

<1901. Find a Peak Element II> (#98)

Approach

2D array이므로 binary search를 하나의 원소가 아닌 하나의 column (또는 row) 에 대해서 수행하면 된다. (난 column 기준으로)

따라서 이전 문제와 동일한 아이디어(#107)를 활용하되, 2D array이므로 상하/좌우를 나누어서 살펴본다.

현재 살펴보고 있는 mid_col에 대해서,

• 상하: mat[...][mid_col] 내에서 가장 큰 값을 가지는 원소의 row index인 max_row를 찾는다. (➡️ O(m))

• 좌우: 다음과 같이 binary search를 적용하여 살펴본다. (➡️ O(logn))

  • mat[max_row][mid_col]이 양 옆의 값보다 크다면 peak로 반환
  • 아니라면 더 큰 값이 있는 쪽으로 탐색 범위 이동

Idea 1: lo <= hi

ref: https://leetcode.com/problems/find-a-peak-element-ii/solutions/1276556/java-python-c-clear-explanation-with-images-m-log-n-very-short-code

이전 문제와 마찬가지로 peak를 찾았을 때 곧바로 반환하기 위해서는 <= 조건이 더 직관적이다.

row, col = len(mat), len(mat[0])

lo_col, hi_col = 0, col - 1

while lo_col <= hi_col:
    mid_col = (lo_col + hi_col) // 2
    ...

• 상하: 단순하게 가장 큰 값을 가지는 원소를 찾는다.

  # [상하] mid_col 내에서 가장 큰 값을 가지는 row 번호 찾기
  max_row = 0
  for r in range(row):
    if mat[r][mid_col] > mat[max_row][mid_col]:
        max_row = r

• 좌우: mat[max_row][mid_col]를 mat[max_row][mid_col - 1], mat[max_row][mid_col + 1]와 비교할 때, 해당 값들이 search range 안에 속하는지 여부도 가독성 좋게 반영하기 위해서 다음과 같은 변수를 설정한다.

  # [좌우] mid_col 내에서 가장 큰 값을 기준으로, 왼쪽 col과 오른쪽 col 비교하기 (boundary 및 크기)
  left_is_big = lo_col <= mid_col - 1 and mat[max_row][mid_col - 1] > mat[max_row][mid_col]
  right_is_big = mid_col + 1 <= hi_col and mat[max_row][mid_col + 1] > mat[max_row][mid_col]

• search range를 좁혀나가는 로직은 다음과 같이 작성할 수 있다.

  # left와 right 모두 mid 보다 크지 않거나, 더이상 비교할 원소가 없다면 peak 발견
  if not left_is_big and not right_is_big:
    return [max_row, mid_col]
  # peak를 발견하지 못했다면, 더 큰 값이 있는 구간으로 이동
  elif right_is_big:
    lo_col = mid_col + 1
  else:
    hi_col = mid_col - 1

Idea 2: lo < hi

ref: https://leetcode.com/problems/find-a-peak-element-ii/solutions/1275904/java-clean-code-with-explanation-o-nlgm

이전 문제와 마찬가지로, lo < hi 로직으로 더 간결한 로직을 작성할 수도 있다.

• 우선, 편의를 위해 [상하]를 살펴보기 위해 mid_col 내에서 가장 큰 값을 가지는 row 번호를 찾는 함수를 정의했다.

  def get_max_row_idx(c):
    """column index가 c인 column 내에서 최댓값의 row index 반환"""
    max_row = 0
    for r in range(row):
        if mat[r][c] > mat[max_row][c]:
            max_row = r
    return max_row

• lower mid를 사용한다면 다음과 같이 mid_col + 1하고만 비교(mat[max_row][mid_col] > mat[max_row][mid_col + 1])하면 된다.

  while lo_col < hi_col:
    mid_col = (lo_col + hi_col) // 2    # lower mid
  
    # [상하] mid_col 내에서 가장 큰 값을 가지는 row 번호 찾기
    max_row = get_max_row_idx(mid_col)
  
    # [좌우] mid_col의 값이 오른쪽 값보다 크면, 해당 값까지 포함하여 왼쪽 탐색
    if mat[max_row][mid_col] > mat[max_row][mid_col + 1]:
        hi_col = mid_col    # include mid_col & look for left
    else:
        lo_col = mid_col + 1

• 하지만 이번 문제는 2D 문제이므로 lo == hi가 되기 직전에 lo_col이 업데이트 된 경우를 위해, 결과 값을 반환하기 전 현재의 lo_col 내에서의 max_row index를 다시 구해주어야 한다. (❗)

  # 직전에 lo_col이 업데이트 된 경우를 위해, 현재 lo_col 내에서 max_row index 구하기
  max_row = get_max_row_idx(lo_col)
  
  return [max_row, lo_col]

Complexity

• Time: O(m * logn) (mat가 m * n이라면, [상하] O(m), [좌우] O(logn))
• Space: O(1)