Watch 10 video solutions for Destroy Sequential Targets, a medium level problem involving Array, Hash Table, Counting. This walkthrough by Bro Coders has 1,534 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed array nums consisting of positive integers, representing targets on a number line. You are also given an integer space.
You have a machine which can destroy targets. Seeding the machine with some nums[i] allows it to destroy all targets with values that can be represented as nums[i] + c * space, where c is any non-negative integer. You want to destroy the maximum number of targets in nums.
Return the minimum value of nums[i] you can seed the machine with to destroy the maximum number of targets.
Example 1:
Input: nums = [3,7,8,1,1,5], space = 2 Output: 1 Explanation: If we seed the machine with nums[3], then we destroy all targets equal to 1,3,5,7,9,... In this case, we would destroy 5 total targets (all except for nums[2]). It is impossible to destroy more than 5 targets, so we return nums[3].
Example 2:
Input: nums = [1,3,5,2,4,6], space = 2 Output: 1 Explanation: Seeding the machine with nums[0], or nums[3] destroys 3 targets. It is not possible to destroy more than 3 targets. Since nums[0] is the minimal integer that can destroy 3 targets, we return 1.
Example 3:
Input: nums = [6,2,5], space = 100 Output: 2 Explanation: Whatever initial seed we select, we can only destroy 1 target. The minimal seed is nums[1].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= space <= 109Problem Overview: You are given an array of integers representing targets and an integer space. Choosing a number destroys every target that differs from it by multiples of space. The task is to pick the starting value that destroys the maximum number of targets, returning the smallest such number.
Approach 1: Modulo Grouping Approach (O(n) time, O(n) space)
The key observation is that numbers that differ by multiples of space share the same remainder when divided by space. If two values have num % space equal, they belong to the same destroyable chain. Iterate through the array once and maintain a hash map counting how many numbers appear for each remainder. While counting, track the smallest value belonging to the remainder group with the highest frequency. This uses constant-time hash lookups and avoids sorting, giving linear runtime. This approach relies on a hash table for grouping and works well for large inputs where sorting would be unnecessary overhead.
Approach 2: Frequency Counting with Sorting (O(n log n) time, O(n) space)
Another way to reason about the same grouping is to sort the array first. Sorting ensures you encounter smaller values earlier, which simplifies picking the smallest valid answer when multiple groups have equal size. After sorting, iterate through the array and compute num % space, storing frequencies in a map. For each remainder group, update the best answer if its count exceeds the previous maximum. Sorting adds O(n log n) overhead but keeps the implementation straightforward, especially in languages where ordered traversal helps with tie-breaking. This approach combines array traversal with counting using a map.
Recommended for interviews: The modulo grouping approach is the expected optimal solution. It demonstrates the key mathematical insight that sequential targets share the same remainder when divided by space. Showing the sorted counting version first can help explain the grouping idea, but the linear-time hash map solution proves you recognize the optimization and can implement it efficiently.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Modulo Grouping with Hash Map | O(n) | O(n) | Best general solution. Avoids sorting and scales well for large arrays. |
| Frequency Counting with Sorting | O(n log n) | O(n) | Useful when sorted order simplifies tie-breaking or debugging. |