Day 02 & 03: Coding Problems

I solved 6 problems from topic Stack, Linear Search, and Recursion:

1. Asteroid Collision (Stack)
2. Kth Missing Positive Number (Linear Search)
3. Subset Sums (Recursion)
4. Subset-II (Recursion)
5. Combination sum-1 (Recursion)
6. Combination sum-2 (Recursion)

Problem 1: Asteroid Collision

Context

The problem involves an array of integers representing asteroids, where the absolute value indicates the size and the sign suggests direction (positive for right, negative for left). Asteroids moving towards each other will collide: the smaller one explodes, and if they're equal in size, both explode. The task is to determine the final state of the array after all collisions.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code simulates collisions between asteroids moving in opposite directions. It uses a stack to manage these collisions. Here's what the code does:

1. It iterates through the asteroid array.
2. For each asteroid, if it moves left (negative) and the stack's top asteroid moves right (positive), a collision occurs: The smaller asteroid explodes. If they are equal in size, both explode.
3. It should be noted that if the stack's top asteroid is negative and the current asteroid is positive, they are moving in different directions and will never collide.
4. Non-exploded asteroids are pushed onto the stack.
5. After processing all asteroids, the stack contents are reversed and stored in a result vector, representing the final state after all collisions.
6. The function returns this result vector.

Problem 2: Kth Missing Positive Number

Context

The problem involves finding the kth positive integer missing from a given array of positive integers sorted in strictly increasing order. The goal is to identify which positive integers are absent from the sequence and return the kth one in this list of missing integers.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code finds the kth missing positive integer from a sorted array of positive integers using a linear search approach. Here's what the code does:

1. It initializes counters for missing numbers (c) and for traversing the array (j).
2. It iterates over integers starting from 1, checking if each integer is in the array: If the integer is missing from the array, it increments the missing counter (c). If the integer is present in the array, it moves to the next array element.
3. When the counter reaches, it returns the current integer as the kth missing number.
4. If the kth missing number is not found within the array's range, it continues searching beyond the array's largest element until it finds the kth missing number.

This linear search ensures all potential missing numbers are checked sequentially.

Problem 3: Subset Sums

Context

The problem requires finding the sums of all possible subsets of a given list of n integers. The output should be a list of these sums, which can be printed in any order.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code finds the sums of all possible subsets of a list of integers using a recursive approach. Here’s what the code does:

1. The code uses a recursive approach to explore all possible subsets of the array.
2. For each element, it explores two possibilities: including the element in the current subset or not including it.
3. When the end of the array is reached, the sum of the current subset is recorded.
4. This approach generates all subsets by picking and not picking each element and collects their sums.

Overall, the function explores all possible subsets and computes their sums efficiently using recursion.

Problem 4: Subset-II

Context

The problem requires generating all possible subsets (the power set) from a given integer array 'nums' that may contain duplicates. The solution must ensure that no duplicate subsets are included in the result. The subsets can be returned in any order.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a recursive approach to generate all unique subsets of a list of integers that may contain duplicates. Here’s what the code does:

1. It explores two options for each element: including it in the current subset or excluding it.
2. To handle duplicates, after including an element, it skips over any subsequent duplicate elements to ensure that duplicate subsets are not generated.
3. This approach ensures that all subsets are considered, and duplicates are avoided by leveraging sorting and skipping duplicates.
4. When the end of the array is reached (ind == nums.size()), the current subset (ds) is added to the result vector 'ans'.

The code ensures that all unique subsets are generated efficiently by carefully managing the inclusion and exclusion of elements and handling duplicates appropriately.

Problem 5: Combination Sum-1

Context

The problem requires finding all unique combinations of integers from a given array candidates that sum up to a target integer target. Each number in the array can be used multiple times in the combinations. The result should include all unique combinations where the sum equals the target, and each combination should be distinct based on the frequency of the numbers used. The number of unique combinations is guaranteed to be fewer than 150.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a recursive backtracking approach to explore all possible unique combinations of integers from a list 'candidates' that sum up to a target. Here’s what the code does:

1. It picks an element if it is less than or equal to the remaining target and recursively tries to build the combination with that element.
2. After considering the current element, it backtracks by removing the element and then tries to find combinations without including the current element.
3. When the target becomes zero, the current combination 'ds' is added to the result 'ans'.

This approach ensures that all possible combinations that sum up to the target are found, and each combination is unique based on the frequency of the numbers used.

Problem 6: Combination Sum-2

Context

The problem is to find all unique combinations of numbers from a given collection candidates that sum up to a target number target. Each number in candidates can be used only once in each combination. The solution must avoid duplicate combinations and return all possible unique combinations that sum to the target.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a recursive backtracking approach to find all unique combinations of numbers from a collection candidates that sum up to a target, with each number used at most once per combination. Here’s what the code does:

Sorting: The array is sorted to handle duplicates and to optimize the loop's early termination.

For Loop:

?? Skip Duplicates: Prevents duplicate combinations by skipping identical elements.

?? Break Condition: Improves efficiency by breaking the loop when the current element exceeds the target, which is more efficient than exploring all possibilities, including those where the element exceeds the target.

Recursive Backtracking:

?? Include and Exclude: Uses the for loop to decide whether to include or exclude each element efficiently, avoiding the complexity of exploring invalid combinations that exceed the target.

This approach is more efficient than a simple pick-not-pick approach, which could explore unnecessary combinations where elements exceed the target. The for-loop approach effectively reduces the complexity by leveraging sorting and breaking conditions.

Here are the three problems I solved today and yesterday. I look forward to sharing more coding challenges with you tomorrow??