LeetCode, Day-4/365 Coding Journey

Today, I tackled two interesting problems on LeetCode. Here’s a breakdown of the problems, solutions, and my learnings.

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:

1. Built a left_prod array storing cumulative products from the start.
2. Built a right_prod array storing cumulative products from the end.
3. 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:

1. Initialized a reachable variable to track the farthest index reachable at any point.
2. Updated reachable based on the current index and jump length.
3. Returned False if the current index exceeded reachable.

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.