Problem 1: Product of Array Except Self (LeetCode #238)
Problem Description:
Given an array nums
, return an array such that each element at index i
is the product of all numbers in the array except nums[i]
. You must do this without division and in O(n) time.
Solution in Python:
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
left_prod = [1] * n
right_prod = [1] * n
result = [0] * n
# Calculate left product
for i in range(1, n):
left_prod[i] = left_prod[i - 1] * nums[i - 1]
# Calculate right product
for i in range(n - 2, -1, -1):
right_prod[i] = right_prod[i + 1] * nums[i + 1]
# Calculate the result
for i in range(n):
result[i] = left_prod[i] * right_prod[i]
return result
Time Complexity:
- O(n): Three passes over the array (left product, right product, and result calculation).
Space Complexity:
- O(n): Uses two auxiliary arrays for left and right products.
My Approach:
- Built a
left_prod
array storing cumulative products from the start. - Built a
right_prod
array storing cumulative products from the end. - Combined these arrays to compute the final result.
Learnings:
- Prefix and suffix computations are a great way to solve problems with constraints like “without division.”
- Efficient use of arrays and minimal passes can significantly optimize space and time.
Other Approaches:
- Optimize space by using the result array instead of separate left and right arrays (reduces space complexity to O(1)).
Real-Life Uses:
- Stock analysis: Calculate performance excluding specific days.
- Simulations: Compute aggregated values excluding certain entities.
Problem 2: Jump Game (LeetCode #55)
Problem Description:
Given an array nums
, where each element represents the maximum jump length at that position, determine if you can reach the last index starting from the first index.
Solution in Python:
class Solution:
def canJump(self, nums: List[int]) -> bool:
reachable = 0
for i in range(len(nums)):
if reachable < i:
return False
reachable = max(reachable, i + nums[i])
return True
Time Complexity:
- O(n): Iterates through the array once.
Space Complexity:
- O(1): Uses a single variable to track the farthest reachable index.
My Approach:
- Initialized a
reachable
variable to track the farthest index reachable at any point. - Updated
reachable
based on the current index and jump length. - Returned
False
if the current index exceededreachable
.
Learnings:
- Greedy algorithms simplify problems with step-by-step constraints.
- Dynamic boundary tracking eliminates the need for backtracking or extra space.
Other Approaches:
- Backtracking: Try all possible jump combinations (inefficient for large inputs).
- Dynamic programming: Compute reachability for each index (O(n²)).
Real-Life Uses:
- Game development: Determine level completion paths in platformer games.
- Logistics: Evaluate delivery feasibility based on fuel constraints or distances.
A big thank you to iCodeGuru and its moderators for their guidance and support. Let’s continue coding, learning, and growing together! Feel free to share your insights or discuss these problems.