* Leetcode
:PROPERTIES:
:ANKI_DECK: soft-eng::leetcode
:END:

** 200, Number of Islands                                          :leetcode:
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764727667098
:ANKI_NOTE_HASH: 4515e6de1d46703c314e57ec95236a76
:ANKI_PREPEND_HEADING: t
:END:

*** Text

200, Number of Islands

#+BEGIN_SRC python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = set()
        count = 0
        m = len(grid)
        n = len(grid[0])

        def bfs(r, c):
            {{c1::q = deque()
            visited.add((r,c))
            q.append((r,c))}}

            while q:
                row, col = {{c2::q.popleft()}}
                directions = [[1,0],[0,1],[-1,0], [0,-1]]
                for dr, dc in directions:
                    r, c = row + dr, col + dc
                    if (r in range(m) and c in range(n) and grid[r][c] == "1" and (r,c) not in visited):
                        {{c2::q.append((r,c))}}
                        visited.add((r,c))


        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1' and (i,j) not in visited:
                    count += 1
                    bfs(i,j)

        return count
#+END_SRC

*** Back Extra


** 121, Best time to buy and sell stock
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1764731250419
:ANKI_NOTE_HASH: d39e1d7011c0254aeb8e1bbb2f4b5b8f
:END:

*** Text

121, Best time to buy and sell stock

#+begin_src python
  def maxProfit(prices):
      l, r = 0, 1

      maxP = 0

      while {{c1::r!=len(prices)}}:
          if prices[l] < prices[r]:
              {{c1::prof = prices[r] - prices[l]
              maxP = max(maxP, prof)}}

          else:
              {{c2::l = r

          r += 1}}

      return maxP
#+end_src

*** Back Extra

** 977, Squares of a sorted array
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1764927405284
:ANKI_NOTE_HASH: 8db7c765a4d43f8a3cb743a1d7a47b69
:END:

*** Text

977, Squares of a sorted array

#+begin_src python
  class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        {{c1::answer = collections.deque()
        l, r = 0, len(nums) - 1}}
    
        while l <= r:#O(n)
            {{c2::left, right = abs(nums[l]), abs(nums[r])}}
            {{c3::if left > right:
                answer.appendleft(left * left)
                l += 1}}
            {{c4::else:
                answer.appendleft(right * right)
                r -= 1}}
        return list(answer)
            
#+end_src

*** Back Extra

** 845, Longest Mountain in Array
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1764948922363
:ANKI_NOTE_HASH: 50c1b70b60143416c7f303ef753d5392
:END:

*** Text

845, Longest Mountain in Array

#+begin_src python
class Solution:
    def longestMountain(self, arr: List[int]) -> int:
        max_length = 0

        {{c1::for i in range(1, len(arr) - 1):}}
            {{c2::if arr[i-1] < arr[i] > arr[i+1]:}}
                l = r = i
                {{c3::while l > 0 and arr[l] > arr[l-1]:
                    l -= 1
                while r < len(arr)-1 and arr[r] > arr[r+1]:
                    r += 1 # keep climbing up}}
                
                {{c4::max_length = max(max_length, r - l + 1)}}

        return max_length        
        
#+end_src

*** Back Extra

** 219, Contains Duplicate II
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1765260303161
:ANKI_NOTE_HASH: 781054e4fd9e42f57102cf1b07b06ada
:ANKI_PREPEND_HEADING: t
:END:

*** Text

219, Contains Duplicate II

#+begin_src python
  class Solution:
      def containsNearbyDuplicate(self, nums, k) -> bool:
          {{c4::seen = set()
          for i, num in enumerate(nums):}}
              {{c1::if num in seen:
                  return True}}
              {{c2::seen.add(num)}}
              {{c3::if len(seen) > k:
                  seen.remove(nums[i-k])}}
          {{c5::return False}}
#+end_src

*** Back Extra

recall that the input is =nums= array with integer =k= such that we want =abs(i-j)<=k= and =nums[i]==nums[j]= without =i==j=.


** 1200, Minimum Absolute Difference
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1765262991853
:ANKI_NOTE_HASH: 3d331c0a54c0b1732f2310dd8c61880d
:END:

*** Text

1200, Minimum Absolute Difference

#+begin_src python
class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        mins = []
        arr.sort() # O(n log n)
        l, r = 0, 1
        dif = max(arr) - min(arr)
        while r < len(arr):
            {{c5::a, b = arr[l], arr[r]
            cur_dif = b - a}}
            {{c2::if cur_dif < dif:
                mins = []
                mins.append((a, b))}}
            {{c3::elif cur_dif == dif:
                mins.append((a, b))}}
            {{c1::dif = min(dif, cur_dif)}}
            {{c4::r += 1
            l += 1}}
        return mins
#+end_src

*** Back Extra

recall that for input =[4,2,1,3]= we want output =[(1,2), (2,3), (3,4)]=


** 209, Minimum Size Subarray Sum
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1765265401384
:ANKI_NOTE_HASH: cba55e92de1ee347061a90e345821127
:END:

*** Text

209, Minimum Size Subarray Sum

#+begin_src python
  def minSubArrayLen(self, target: int, nums: List[int]) -> int:
      {{c1::l = 0
      total = 0
      res = float('inf')}}

      {{c2::for r in range(len(nums)):
          total += nums[r]}}

          {{c3::while total >= target:
              res = min(res, r-l+1)

              total -= nums[l]

              l+=1}}
      {{c4::if res == float('inf'):
          return 0
      else:
          return res}}
#+end_src

*** Back Extra

Input: =target = 7, nums = [2,3,1,2,4,3]=
Output: =2=
Explanation: The subarray [4,3] has the minimal length under the problem constraint.


note, the 'problem constraint' is that we must return the /minimal length/ of a subarray whose sum is greater than or equal to =target=