COMPETITIVE PROGRAMMING TASKS 1 (SOLUTIONS)
Sure! Here’s a step-by-step solution for each of the tasks I listed.
### Task 1: FizzBuzz Variation
**Function**: `fizzbuzz(n: int) -> List[str]`
**Steps**:
1. Initialize an empty list `result`.
2. Loop through numbers from 1 to `n`.
3. For each number:
- If divisible by 3 and 5, append "FizzBuzz".
- If divisible by 3, append "Fizz".
- If divisible by 5, append "Buzz".
- Otherwise, append the number as a string.
4. Return the `result`.
**Example Code**:
```python
def fizzbuzz(n: int) -> List[str]:
result = []
for i in range(1, n + 1):
if i % 3 == 0 and i % 5 == 0:
result.append("FizzBuzz")
elif i % 3 == 0:
result.append("Fizz")
elif i % 5 == 0:
result.append("Buzz")
else:
result.append(str(i))
return result
```
### Task 2: Anagram Checker
**Function**: `are_anagrams(s1: str, s2: str) -> bool`
**Steps**:
1. Remove spaces and convert both strings to lowercase.
2. Sort the characters of both strings.
3. Compare the sorted versions.
**Example Code**:
```python
def are_anagrams(s1: str, s2: str) -> bool:
s1 = s1.replace(" ", "").lower()
s2 = s2.replace(" ", "").lower()
return sorted(s1) == sorted(s2)
```
### Task 3: Two Sum Problem
**Function**: `two_sum(nums: List[int], target: int) -> List[int]`
**Steps**:
1. Create a dictionary to store indices of numbers.
2. Loop through `nums`:
- Calculate the complement needed to reach `target`.
- If the complement is in the dictionary, return its index and the current index.
- Otherwise, add the number and its index to the dictionary.
**Example Code**:
```python
def two_sum(nums: List[int], target: int) -> List[int]:
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
```
### Task 4: Longest Substring Without Repeating Characters
**Function**: `length_of_longest_substring(s: str) -> int`
**Steps**:
1. Use a sliding window with two pointers.
2. Maintain a set to track characters in the current substring.
3. Expand the right pointer, adding characters to the set.
4. If a character is repeated, move the left pointer until the substring is valid.
5. Track the maximum length found.
**Example Code**:
```python
def length_of_longest_substring(s: str) -> int:
char_set = set()
left = max_length = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length
```
### Task 5: Merge Intervals
**Function**: `merge_intervals(intervals: List[List[int]]) -> List[List[int]]`
**Steps**:
1. Sort intervals by the start time.
2. Initialize a merged list with the first interval.
3. Loop through sorted intervals:
- If the current interval overlaps with the last merged one, merge them.
- Otherwise, add the current interval to the merged list.
4. Return the merged list.
**Example Code**:
```python
def merge_intervals(intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last_merged = merged[-1]
if current[0] <= last_merged[1]: # Overlapping intervals
last_merged[1] = max(last_merged[1], current[1])
else:
merged.append(current)
return merged
```
### Task 6: Knapsack Problem (0/1)
**Function**: `knapsack(weights: List[int], values: List[int], W: int) -> int`
**Steps**:
1. Initialize a DP array of size `W + 1` with zeros.
2. Iterate over each item:
- Update the DP array in reverse order to avoid overwriting values.
3. Return the last element of the DP array.
**Example Code**:
```python
def knapsack(weights: List[int], values: List[int], W: int) -> int:
dp = [0] * (W + 1)
for i in range(len(weights)):
for w in range(W, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]
```
### Task 7: Count Inversions
**Function**: `count_inversions(arr: List[int]) -> int`
**Steps**:
1. Implement a modified merge sort that counts inversions.
2. During the merge step, count how many elements from the right half are less than elements in the left
half.
**Example Code**:
```python
def merge_and_count(arr, temp_arr, left, mid, right):
i = left # Starting index for left subarray
j = mid + 1 # Starting index for right subarray
k = left # Starting index to be sorted
inv_count = 0
while i <= mid and j <= right:
if arr[i] <= arr[j]:
temp_arr[k] = arr[i]
i += 1
else:
temp_arr[k] = arr[j]
inv_count += (mid - i + 1) # Count inversions
j += 1
k += 1
while i <= mid:
temp_arr[k] = arr[i]
i += 1
k += 1
while j <= right:
temp_arr[k] = arr[j]
j += 1
k += 1
for i in range(left, right + 1):
arr[i] = temp_arr[i]
return inv_count
def merge_sort_and_count(arr, temp_arr, left, right):
inv_count = 0
if left < right:
mid = (left + right) // 2
inv_count += merge_sort_and_count(arr, temp_arr, left, mid)
inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right)
inv_count += merge_and_count(arr, temp_arr, left, mid, right)
return inv_count
def count_inversions(arr: List[int]) -> int:
temp_arr = [0] * len(arr)
return merge_sort_and_count(arr, temp_arr, 0, len(arr) - 1)
```
### Task 8: Minimum Path Sum
**Function**: `min_path_sum(grid: List[List[int]]) -> int`
**Steps**:
1. Initialize a DP table with the same dimensions as `grid`.
2. Set the starting position.
3. Fill in the first row and column.
4. Iterate through the rest of the grid:
- Each cell will be the min of the top and left cells plus its own value.
5. Return the value at the bottom-right corner.
**Example Code**:
```python
def min_path_sum(grid: List[List[int]]) -> int:
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
dp = [[0] * cols for _ in range(rows)]
dp[0][0] = grid[0][0]
for i in range(1, rows):
dp[i][0] = dp[i - 1][0] + grid[i][0]
for j in range(1, cols):
dp[0][j] = dp[0][j - 1] + grid[0][j]
for i in range(1, rows):
for j in range(1, cols):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
return dp[-1][-1]
```
### Task 9: Palindrome Partitioning
**Function**: `palindrome_partition(s: str) -> List[List[str]]`
**Steps**:
1. Use backtracking to explore all partitions.
2. For each substring, check if it's a palindrome.
3. If it is, add it to the current partition and recursively call for the rest of the string.
4. If at the end of the string, add the current partition to the result.
**Example Code**:
```python
def is_palindrome(s: str) -> bool:
return s == s[::-1]
def backtrack(s: str, start: int, path: List[str], result: List[List[str]]):
if start == len(s):
result.append(path.copy())
return
for end in range(start + 1, len(s)
+ 1):
if is_palindrome(s[start:end]):
path.append(s[start:end])
backtrack(s, end, path, result)
path.pop()
def palindrome_partition(s: str) -> List[List[str]]:
result = []
backtrack(s, 0, [], result)
return result
```
### Task 10: Largest Rectangle in Histogram
**Function**: `largest_rectangle_area(heights: List[int]) -> int`
**Steps**:
1. Use a stack to keep track of the indices of the bars in the histogram.
2. Loop through each bar:
- While the stack is not empty and the current height is less than the height of the bar at the index
stored at the top of the stack:
- Pop from the stack and calculate the area.
- Push the current index onto the stack.
3. After finishing the loop, empty the stack to calculate the remaining areas.
4. Return the maximum area found.
**Example Code**:
```python
def largest_rectangle_area(heights: List[int]) -> int:
stack = []
max_area = 0
heights.append(0) # Sentinel value to flush the stack
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
return max_area
```
These step-by-step solutions should help you understand how to approach each problem systematically.
Let me know if you need further explanations or help with any specific task!
