Array

Array: A Complete Guide for Coding Interviews

1. Basic Concept of Arrays

An array is one of the most fundamental and powerful data structures, storing variables of the same type under one name in a sequential manner. Since data is stored in contiguous memory locations, it allows fast access via indexing.

Characteristics of Arrays

• Indexing: Direct access to each element by an index starting from 0 (Time complexity O(1))
• Fixed Size: In most languages, the size of an array is fixed at the time of declaration (dynamic arrays are an exception)
• Same Data Type: A single array can only store elements of the same data type

Time Complexity of Arrays

Operation	Time Complexity
Access	O(1)
Search	O(n)
Insert	O(n)
Delete	O(n)

2. Core Techniques for Arrays

Two Pointers

A technique using two pointers to traverse an array. It is especially effective with sorted arrays.

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
            
    return [-1, -1]  # If no matching pair is found

Sliding Window

A technique that moves a fixed-size or variable-size window over an array to solve problems.

def max_sum_subarray(nums, k):
    # Find the maximum sum of a subarray of size k
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum = window_sum + nums[i] - nums[i-k]  # Move the window
        max_sum = max(max_sum, window_sum)
        
    return max_sum

Prefix Sum

A technique for quickly calculating the sum of contiguous sections of an array.

def range_sum(nums, queries):
    # Calculate the sum for queries (start, end) in O(1) after preprocessing
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)
    
    results = []
    for start, end in queries:
        results.append(prefix[end+1] - prefix[start])
    
    return results

3. Major Array Algorithm Patterns

1) Array Traversal

Example Problem: Maximum Subarray Sum

Problem: Given an integer array, find the sum of the contiguous subarray that has the largest sum.

Solution: Kadane’s Algorithm (Dynamic Programming)

Detailed Explanation of Kadane’s Algorithm

Kadane’s algorithm is the most efficient algorithm for finding the maximum subarray sum in an array. It uses the principles of dynamic programming to solve the problem in O(n) time.

Key Idea:

• Compute the maximum subarray sum ending at each position.
• When encountering a new element, choose between:
  1. Starting a new subarray with this element
  2. Adding this element to the existing subarray

Algorithm Steps:

1. Use two variables: current_sum (the running sum of the current subarray) and max_sum (the maximum subarray sum found so far).
2. Initialize both variables with the first element of the array.
3. Iterate over the remaining elements of the array:
   • Update current_sum = max(num, current_sum + num).
   • Update max_sum = max(max_sum, current_sum).
4. Return the final max_sum.

Example Execution: For the array [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Index	Element	current_sum	max_sum	Explanation
0	-2	-2	-2	Initial values
1	1	1	1	1 is bigger than -2 + 1 = -1
2	-3	-2	1	1 + (-3) = -2, max_sum remains 1
3	4	4	4	4 is bigger than -2 + 4 = 2
4	-1	3	4	4 + (-1) = 3, max_sum still 4
5	2	5	5	3 + 2 = 5, update max_sum to 5
6	1	6	6	5 + 1 = 6, update max_sum to 6
7	-5	1	6	6 + (-5) = 1, max_sum remains 6
8	4	5	6	1 + 4 = 5, max_sum remains 6

Final result: 6 (subarray [4, -1, 2, 1] from index 3 to 6)

Implementation:

def max_subarray_sum(nums):
    if not nums:
        return 0
        
    current_sum = max_sum = nums[0]
    
    for num in nums[1:]:
        # Determine whether to start new with the current element 
        # or add it to the existing subarray
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
        
    return max_sum

Tracking the Subarray Indices: To also track the position of the subarray, implement it as follows:

def max_subarray_with_indices(nums):
    if not nums:
        return 0, -1, -1
    
    current_sum = max_sum = nums[0]
    start = max_start = max_end = 0
    
    for i in range(1, len(nums)):
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            start = i
        else:
            current_sum += nums[i]
        
        if current_sum > max_sum:
            max_sum = current_sum
            max_start = start
            max_end = i
    
    return max_sum, max_start, max_end

Extension: Maximum Subarray Sum in a Circular Array For a circular array, the approach can be modified:

1. Apply Kadane’s algorithm to find the maximum subarray sum.
2. Compute (total sum of the array) – (minimum subarray sum) to account for wrapping around the ends.
3. Take the maximum of those two results.

Time Complexity: O(n)
Space Complexity: O(1)

2) Array Rearrangement

Example Problem: Sort Colors (Dutch National Flag Problem) – LeetCode #75

Problem: Given an array with only 0s, 1s, and 2s, sort it in ascending order. (Often referred to as the red, white, and blue flag problem)

Solution: Use three pointers.

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    
    while mid <= high:
        if nums[mid] == 0:  # Red (0)
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:  # White (1)
            mid += 1
        else:  # Blue (2)
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Time Complexity: O(n)
Space Complexity: O(1)

More Array Rearrangement Problems:

1. Array Partition – LeetCode #561
   • For an array of size 2n, split it into n pairs so that the sum of the minimum of each pair is maximized.
2. Moving Zeros (0 and 1 Rearrangement) – LeetCode #283 (Move Zeroes)
   • Move all 0s to the end of the array while maintaining the relative order of the other elements.
3. Rotate Array – LeetCode #189
   • Rotate the array to the right by k steps.

3) Array Search

Example Problem: Find Peak Element – LeetCode #162

Problem: Find an element in the array that is greater than its adjacent elements (a peak).

Solution: Modified Binary Search

def find_peak_element(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if nums[mid] > nums[mid + 1]:
            # Descending slope starts, so the peak must be on the left
            right = mid
        else:
            # Ascending slope, so the peak must be on the right
            left = mid + 1
            
    return left  # Index of the peak

Time Complexity: O(log n)
Space Complexity: O(1)

More Array Search Problems:

1. Search in Rotated Sorted Array – LeetCode #33
   • Find the index of a target value in a rotated sorted array.
2. Median of Two Sorted Arrays – LeetCode #4
   • Given two sorted arrays, find the median of the combined data.
3. Find Minimum in Rotated Sorted Array – LeetCode #153
   • Find the minimum element in a rotated sorted array.
4. First Missing Positive – LeetCode #41
   • Find the smallest missing positive integer in an unsorted array.

4. Advanced Array Techniques

1) Array Rotation – LeetCode #189

Rotating an array around a specific pivot.

def rotate_array(nums, k):
    n = len(nums)
    k = k % n  # k can be larger than n
    
    # Reverse the entire array
    nums.reverse()
    
    # Reverse the first k elements
    nums[:k] = reversed(nums[:k])
    
    # Reverse the remaining elements
    nums[k:] = reversed(nums[k:])

Related LeetCode Problems:

• Rotate Array – LeetCode #189
• Rotate String – LeetCode #796
• Rotate Image – LeetCode #48

2) Monotonic Stack – LeetCode #739

A stack that maintains elements in increasing or decreasing order to efficiently find the next greater or smaller element.

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # Default value -1 (no next greater element)
    stack = []
    
    for i in range(n):
        # While stack is not empty and current element is greater than the top element of the stack
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result

Related LeetCode Problems:

• Daily Temperatures – LeetCode #739
• Next Greater Element I – LeetCode #496
• Next Greater Element II – LeetCode #503
• Largest Rectangle in Histogram – LeetCode #84

3) Two Pointers Variations – LeetCode #15

Advanced variations of the two-pointer technique to handle problems with three or more elements.

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        # Avoid duplicates
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                # If sum is 0, add it to result
                result.append([nums[i], nums[left], nums[right]])
                
                # Avoid duplicates
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                    
                left += 1
                right -= 1
                
    return result

Related LeetCode Problems:

• 3Sum – LeetCode #15
• 4Sum – LeetCode #18
• 3Sum Closest – LeetCode #16
• Container With Most Water – LeetCode #11

4) Advanced Sliding Window – LeetCode #76

A technique using a variable-length window to find an optimal subarray.

def min_window_substring(s, t):
    if not s or not t:
        return ""
        
    # Count character frequencies in the target string
    target_counts = {}
    for char in t:
        target_counts[char] = target_counts.get(char, 0) + 1
        
    required = len(target_counts)  # Number of distinct characters needed
    formed = 0  # Number of distinct characters satisfied so far
    
    window_counts = {}
    
    min_len = float('inf')
    result_start = 0
    
    left = right = 0
    
    while right < len(s):
        # Add the character at right pointer
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        # If this character is in target_counts and its frequency is now satisfied
        if char in target_counts and window_counts[char] == target_counts[char]:
            formed += 1
            
        # Try to contract the window if all distinct characters are satisfied
        while left <= right and formed == required:
            char = s[left]
            
            # Update the result if this window is smaller
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result_start = left
                
            # Remove the character at left
            window_counts[char] -= 1
            
            if char in target_counts and window_counts[char] < target_counts[char]:
                formed -= 1
                
            left += 1
            
        right += 1
        
    return "" if min_len == float('inf') else s[result_start:result_start + min_len]

Related LeetCode Problems:

• Minimum Window Substring – LeetCode #76
• Longest Substring Without Repeating Characters – LeetCode #3
• Longest Substring with At Most K Distinct Characters – LeetCode #340
• Fruit Into Baskets – LeetCode #904

5. Practical Coding Interview Problems

Problem 1: Two Sum

Problem: Given an integer array and a target value, return the indices of two elements whose sum equals the target value.

Solution: Use a hashmap.

def two_sum(nums, target):
    num_map = {}  # Map from element value to index
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    
    return [-1, -1]  # If no matching pair is found

Time Complexity: O(n)
Space Complexity: O(n)

Problem 2: Remove Duplicates from an Array

Problem: Given a sorted array, remove the duplicates in-place and return the length of the modified array.

Solution: Two Pointers

def remove_duplicates(nums):
    if not nums:
        return 0
        
    # slow pointer points to the last position of the unique array
    slow = 0
    
    # fast pointer traverses the array
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    
    return slow + 1  # Length of the new array

Time Complexity: O(n)
Space Complexity: O(1)

Problem 3: Best Time to Buy and Sell Stock

Problem: Given an array of stock prices, find the maximum profit that can be achieved by making one transaction.

Solution: Greedy Algorithm

def max_profit(prices):
    if not prices:
        return 0
        
    max_profit = 0
    min_price = prices[0]
    
    for price in prices[1:]:
        # Update the minimum price so far
        min_price = min(min_price, price)
        # Calculate the profit if sold at current price
        max_profit = max(max_profit, price - min_price)
    
    return max_profit

Time Complexity: O(n)
Space Complexity: O(1)

6. Strategy for Solving Array Problems

1) Approach to Array Problems

1. Identify the Category: Understand whether it’s traversal, searching, rearrangement, etc.
2. Check for Applicable Patterns or Formulas: Decide if two pointers, sliding window, etc., can be applied.
3. Consider Sorting: Check if sorting can simplify the problem.
4. Consider Space-Time Trade-offs: Evaluate whether using extra space can reduce time complexity.

2) Tips for Reducing Time Complexity

1. Utilize Input Characteristics: Make use of sorted inputs or limited ranges.
2. Store Intermediate Results: Use memoization or caching to avoid repeated calculations.
3. Apply Mathematical Formulas: If possible, simplify computations with mathematical equations or identities.

7. Summary: Key Formulas and Patterns for Arrays

Technique	Use Cases	Time Complexity
Binary Search	Searching in a sorted array	O(log n)
Two Pointers	Pair-finding, duplicates removal	O(n)
Sliding Window	Contiguous subarray problems	O(n)
Prefix Sum	Range sum queries	Preprocessing O(n), Query O(1)
Kadane’s Algorithm	Maximum subarray sum	O(n)
Monotonic Stack	Finding next greater/smaller element	O(n)

---

배열(Array): 코딩 인터뷰를 위한 완벽 가이드

1. 배열의 기본 개념

배열은 가장 기본적이면서도 강력한 자료구조로, 같은 타입의 변수들을 하나의 이름으로 순차적으로 저장하는 방식입니다. 메모리 상에서 연속적인 공간에 데이터를 저장하므로 인덱스를 통한 빠른 접근이 가능합니다.

배열의 특징

• 인덱싱: 0부터 시작하는 인덱스로 각 요소에 직접 접근 가능 (O(1) 시간복잡도)
• 고정된 크기: 대부분의 언어에서 배열은 선언 시 크기가 고정됨 (동적 배열은 예외)
• 같은 데이터 타입: 하나의 배열은 같은 데이터 타입만 저장 가능

배열 시간복잡도

연산	시간복잡도
접근 (Access)	O(1)
검색 (Search)	O(n)
삽입 (Insert)	O(n)
삭제 (Delete)	O(n)

2. 배열의 핵심 기술

투 포인터 (Two Pointers)

두 개의 포인터를 활용하여 배열을 순회하는 기법입니다. 특히 정렬된 배열에서 효과적입니다.

def two_sum(nums, target):
    left, right = 0, len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
            
    return [-1, -1]  # 해당하는 쌍을 찾지 못한 경우

슬라이딩 윈도우 (Sliding Window)

고정 크기 또는 가변 크기의 윈도우를 배열 위에서 이동시키며 문제를 해결하는 기법입니다. 슬라이딩 윈도우 기법은 크게 3가지로 나뉠 수 있습니다.

1. 윈도우 확장
2. 윈도우 길이 계산
3. 새 문자 인덱스 정보 갱신

이 순서들은 조금씩 달라질 수 있지만 근본적으로는 윈도우를 올바른 상태로 만든 뒤에 결과를 측정한다라는 원리가 있습니다.

def max_sum_subarray(nums, k):
    # k 크기의 연속 부분배열 중 최대 합 찾기
    window_sum = sum(nums[:k])
    max_sum = window_sum
    
    for i in range(k, len(nums)):
        window_sum = window_sum + nums[i] - nums[i-k]  # 윈도우 이동
        max_sum = max(max_sum, window_sum)
        
    return max_sum

프리픽스 합 (Prefix Sum)

배열의 연속 구간 합을 빠르게 계산하기 위한 기법입니다.

def range_sum(nums, queries):
    # 쿼리 (start, end)에 대한 구간 합을 O(1)에 계산
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)
    
    results = []
    for start, end in queries:
        results.append(prefix[end+1] - prefix[start])
    
    return results

3. 주요 배열 알고리즘 문제 패턴

1) 배열 순회 (Array Traversal)

문제 예시: 최대 부분 배열 합 찾기

문제: 정수 배열이 주어졌을 때, 합이 최대가 되는 연속 부분 배열의 합을 찾으시오.

해법: Kadane’s 알고리즘 (동적 계획법)

Kadane’s 알고리즘 상세 설명

Kadane’s 알고리즘은 배열에서 최대 부분 배열 합을 찾는 가장 효율적인 알고리즘입니다. 이 알고리즘은 동적 계획법의 원리를 사용하여 O(n) 시간에 문제를 해결합니다.

핵심 아이디어:

• 각 위치에서 끝나는 최대 부분 배열 합을 계산합니다.
• 새로운 원소를 만날 때마다 두 가지 중 더 큰 값을 선택합니다:
  1. 현재 원소만으로 새로운 부분 배열 시작하기
  2. 현재 원소를 이전 부분 배열에 추가하기

알고리즘 단계:

1. 두 변수 사용: current_sum(현재까지의 부분 배열 합), max_sum(전체 최대 부분 배열 합)
2. 첫 원소로 두 변수 초기화
3. 배열의 남은 원소를 순회하며:
   • current_sum = max(num, current_sum + num)으로 갱신
   • max_sum = max(max_sum, current_sum)으로 갱신
4. 최종 max_sum 반환

예시 실행: 배열 [-2, 1, -3, 4, -1, 2, 1, -5, 4]에 대해:

인덱스	원소	current_sum	max_sum	설명
0	-2	-2	-2	초기값
1	1	1	1	-2+1=-1보다 1만 선택하는 것이 더 큼
2	-3	-2	1	1+(-3)=-2, max_sum 유지
3	4	4	4	-2+4=2보다 4만 선택하는 것이 더 큼
4	-1	3	4	4+(-1)=3, max_sum 유지
5	2	5	5	3+2=5, max_sum 갱신
6	1	6	6	5+1=6, max_sum 갱신
7	-5	1	6	6+(-5)=1, max_sum 유지
8	4	5	6	1+4=5, max_sum 유지

최종 결과: 6 (인덱스 3~6의 부분 배열 [4, -1, 2, 1])

구현 코드:

def max_subarray_sum(nums):
    if not nums:
        return 0
        
    current_sum = max_sum = nums[0]
    
    for num in nums[1:]:
        # 현재 원소를 포함하는 것이 더 큰지, 새로 시작하는 것이 더 큰지 결정
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
        
    return max_sum

최대 부분 배열 위치 추적: 부분 배열의 위치도 함께 추적하려면 다음과 같이 구현합니다:

def max_subarray_with_indices(nums):
    if not nums:
        return 0, -1, -1
    
    current_sum = max_sum = nums[0]
    start = max_start = max_end = 0
    
    for i in range(1, len(nums)):
        # 새로 시작하는 것이 더 나은 경우
        if nums[i] > current_sum + nums[i]:
            current_sum = nums[i]
            start = i
        else:
            current_sum = current_sum + nums[i]
        
        # 최대값 갱신
        if current_sum > max_sum:
            max_sum = current_sum
            max_start = start
            max_end = i
    
    return max_sum, max_start, max_end

확장: 원형 배열의 최대 부분 배열 합 원형 배열(circular array)에서 최대 부분 배열 합을 찾는 문제도 Kadane의 알고리즘을 변형하여 해결할 수 있습니다:

1. 일반 Kadane’s 알고리즘으로 최대 부분 배열 합 계산
2. 전체 배열 합 - 최소 부분 배열 합 계산 (원형으로 감싸는 경우)
3. 위의 두 결과 중 최대값 선택

시간복잡도: O(n)
공간복잡도: O(1)

2) 배열 재배치 (Array Rearrangement)

문제 예시: 색상 정렬 (Dutch National Flag Problem) - LeetCode 75번

문제: 0, 1, 2로만 이루어진 배열을 오름차순으로 정렬하시오. (빨강, 흰색, 파랑 국기 문제)

해법: 3개의 포인터 활용

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    
    while mid <= high:
        if nums[mid] == 0:  # 빨강(0)
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:  # 흰색(1)
            mid += 1
        else:  # 파랑(2)
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

시간복잡도: O(n)
공간복잡도: O(1)

더 많은 배열 재배치 문제:

1. 배열 파티션(Array Partition) - LeetCode 561번
   • 2n 크기의 배열을 n쌍으로 나누어 각 쌍의 최소값 합을 최대화
2. 0과 1로 구성된 배열 재배치 - LeetCode 283번 (Move Zeroes)
   • 0을 배열의 끝으로 이동시키되, 다른 요소들의 상대적 순서 유지
3. 배열 회전(Rotate Array) - LeetCode 189번
   • 배열을 k 단계 오른쪽으로 회전

3) 배열 탐색 (Array Search)

문제 예시: 피크 원소 찾기 - LeetCode 162번 (Find Peak Element)

문제: 배열에서 인접한 원소보다 큰 원소(피크)를 찾으시오.

해법: 이진 탐색 변형

def find_peak_element(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = (left + right) // 2
        
        if nums[mid] > nums[mid + 1]:
            # 내림세가 시작되므로 왼쪽에 피크가 있음
            right = mid
        else:
            # 오르막이므로 오른쪽에 피크가 있음
            left = mid + 1
            
    return left  # 피크 인덱스

시간복잡도: O(log n)
공간복잡도: O(1)

더 많은 배열 탐색 문제:

1. 회전된 정렬 배열에서 검색 - LeetCode 33번 (Search in Rotated Sorted Array)
   • 회전된 정렬 배열에서 타겟 값의 인덱스 찾기
2. 두 정렬된 배열의 중앙값 - LeetCode 4번 (Median of Two Sorted Arrays)
   • 두 정렬된 배열이 주어질 때 전체의 중앙값 찾기
3. 최소값 찾기 (회전된 정렬 배열) - LeetCode 153번 (Find Minimum in Rotated Sorted Array)
   • 회전된 정렬된 배열에서 최소값 찾기
4. 누락된 첫 번째 양수 - LeetCode 41번 (First Missing Positive)
   • 정렬되지 않은 배열에서 누락된 가장 작은 양의 정수 찾기

4. 고급 배열 기법

1) 배열 회전 (Array Rotation) - LeetCode 189번

배열을 특정 위치를 기준으로 회전하는 기법입니다.

def rotate_array(nums, k):
    n = len(nums)
    k = k % n  # k가 n보다 클 수 있음
    
    # 전체 배열 뒤집기
    nums.reverse()
    
    # 앞부분 k개 뒤집기
    nums[:k] = reversed(nums[:k])
    
    # 나머지 부분 뒤집기
    nums[k:] = reversed(nums[k:])

관련 LeetCode 문제:

• 배열 회전 - LeetCode 189번 (Rotate Array)
• 문자열 회전 - LeetCode 796번 (Rotate String)
• 이미지 회전 - LeetCode 48번 (Rotate Image)

2) 모노토닉 스택 (Monotonic Stack) - LeetCode 739번

증가 또는 감소 순서를 유지하는 스택을 사용하여 다음 큰 원소나 다음 작은 원소를 효율적으로 찾습니다.

def next_greater_element(nums):
    n = len(nums)
    result = [-1] * n  # 기본값은 -1 (다음 큰 원소가 없음)
    stack = []
    
    for i in range(n):
        # 스택이 비어있지 않고, 현재 원소가 스택의 top 원소보다 큰 경우
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result

관련 LeetCode 문제:

• 일일 온도 - LeetCode 739번 (Daily Temperatures)
• 다음 더 큰 요소 I - LeetCode 496번 (Next Greater Element I)
• 다음 더 큰 요소 II - LeetCode 503번 (Next Greater Element II)
• 히스토그램에서 가장 큰 직사각형 - LeetCode 84번 (Largest Rectangle in Histogram)

3) 투 포인터 변형 (Two Pointers Variations) - LeetCode 15번

투 포인터 기법의 고급 변형으로, 세 개 이상의 요소를 처리하는 문제에 적용됩니다.

def three_sum(nums):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 2):
        # 중복 제거
        if i > 0 and nums[i] == nums[i-1]:
            continue
            
        # 투 포인터로 나머지 두 수 찾기
        left, right = i + 1, n - 1
        
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                # 합이 0인 경우, 결과에 추가
                result.append([nums[i], nums[left], nums[right]])
                
                # 중복 제거
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                    
                left += 1
                right -= 1
                
    return result

관련 LeetCode 문제:

• 세 수의 합 - LeetCode 15번 (3Sum)
• 네 수의 합 - LeetCode 18번 (4Sum)
• 가장 가까운 세 수의 합 - LeetCode 16번 (3Sum Closest)
• 컨테이너에 가장 많은 물 - LeetCode 11번 (Container With Most Water)

4) 슬라이딩 윈도우 고급 기법 (Advanced Sliding Window) - LeetCode 76번

가변 길이 윈도우를 사용하여 최적의 부분 배열을 찾는 기법입니다.

def min_window_substring(s, t):
    if not s or not t:
        return ""
        
    # 타겟 문자열의 문자 빈도수 계산
    target_counts = {}
    for char in t:
        target_counts[char] = target_counts.get(char, 0) + 1
        
    required = len(target_counts)  # 필요한 고유 문자 수
    formed = 0  # 충족된 고유 문자 수
    
    # 현재 윈도우의 문자 빈도수
    window_counts = {}
    
    # 결과 윈도우 정보
    min_len = float('inf')
    result_start = 0
    
    left = right = 0
    
    while right < len(s):
        # 오른쪽 포인터 문자 추가
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        # 현재 문자가 타겟에 있고, 필요한 빈도수를 만족하면 formed 증가
        if char in target_counts and window_counts[char] == target_counts[char]:
            formed += 1
            
        # 모든 문자 조건이 충족되면 왼쪽 포인터 이동
        while left <= right and formed == required:
            char = s[left]
            
            # 더 짧은 윈도우를 찾으면 결과 갱신
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result_start = left
                
            # 왼쪽 포인터 문자 제거
            window_counts[char] -= 1
            
            # 제거한 문자가 타겟에 있고, 빈도수가 부족해지면 formed 감소
            if char in target_counts and window_counts[char] < target_counts[char]:
                formed -= 1
                
            left += 1
            
        right += 1
        
    return "" if min_len == float('inf') else s[result_start:result_start + min_len]

관련 LeetCode 문제:

• 최소 윈도우 부분 문자열 - LeetCode 76번 (Minimum Window Substring)
• 가장 긴 고유 문자 부분 문자열 - LeetCode 3번 (Longest Substring Without Repeating Characters)
• K가 다른 문자들인 최장 부분 문자열 - LeetCode 340번 (Longest Substring with At Most K Distinct Characters)
• 과일 바구니에 담긴 과일의 총 개수 - LeetCode 904번 (Fruit Into Baskets)

5. 실전 코딩 인터뷰 문제

문제 1: 두 수의 합 (Two Sum)

문제: 정수 배열과 타겟 값이 주어졌을 때, 합이 타겟 값이 되는 두 원소의 인덱스를 반환하시오.

해법: 해시맵 활용

def two_sum(nums, target):
    num_map = {}  # 값 -> 인덱스 매핑
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i
    
    return [-1, -1]  # 해당하는 쌍이 없는 경우

시간복잡도: O(n)
공간복잡도: O(n)

문제 2: 배열에서 중복 제거 (Remove Duplicates)

문제: 정렬된 배열에서 중복을 제거하고, 중복이 제거된 배열의 새 길이를 반환하시오.

해법: 투 포인터 기법

def remove_duplicates(nums):
    if not nums:
        return 0
        
    # slow 포인터는 중복이 제거된 배열의 마지막 위치를 가리킴
    slow = 0
    
    # fast 포인터로 배열을 순회
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    
    return slow + 1  # 새 배열의 길이

시간복잡도: O(n)
공간복잡도: O(1)

문제 3: 주식 거래로 최대 이익 (Best Time to Buy and Sell Stock)

문제: 주식 가격 배열이 주어졌을 때, 한 번의 거래로 얻을 수 있는 최대 이익을 계산하시오.

해법: 그리디 알고리즘

def max_profit(prices):
    if not prices:
        return 0
        
    max_profit = 0
    min_price = prices[0]
    
    for price in prices[1:]:
        # 현재까지의 최소 가격 갱신
        min_price = min(min_price, price)
        # 현재 가격으로 팔 때의 이익 계산
        max_profit = max(max_profit, price - min_price)
    
    return max_profit

시간복잡도: O(n)
공간복잡도: O(1)

6. 배열 문제 해결 전략

1) 배열 문제 접근법

1. 문제 분류 파악하기: 순회, 검색, 재배치 등 문제의 본질적인 유형 파악
2. 공식 및 패턴 적용 가능성 확인: 투 포인터, 슬라이딩 윈도우 등의 패턴 적용 여부 결정
3. 정렬 고려하기: 정렬이 문제 해결을 단순화할 수 있는지 검토
4. 공간-시간 트레이드오프 고려: 추가 공간을 사용하여 시간 복잡도를 개선할 수 있는지 검토

2) 배열 문제 시간 단축 팁

1. 입력 특성 활용: 정렬 여부, 범위 제한 등의 특성 활용
2. 중간 계산 저장: 중복 계산을 피하기 위해 중간 결과 저장 (메모이제이션)
3. 수학적 공식 적용: 가능한 경우 수학적 공식을 활용하여 계산 단순화

7. 요약: 배열 핵심 공식 및 패턴

기법	적용 상황	시간복잡도
이진 탐색	정렬된 배열에서 원소 검색	O(log n)
투 포인터	쌍 찾기, 중복 제거	O(n)
슬라이딩 윈도우	연속 부분 배열 문제	O(n)
프리픽스 합	구간 합 쿼리	전처리 O(n), 쿼리 O(1)
Kadane’s 알고리즘	최대 부분 배열 합	O(n)
모노토닉 스택	다음 큰/작은 원소 찾기	O(n)