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.
By considering each number modulo space, we can group numbers into equivalence classes based on their remainder when divided by space. For a given number, all other numbers it can destroy have the same remainder modulo space. We can use this grouping to determine the largest group and select the smallest number from it to satisfy the conditions of the problem.
This solution groups each number in nums by its remainder when divided by space. It uses a dictionary to count how many numbers fall into each group. Then, it finds the group with the most numbers and selects the smallest number from that group. This approach ensures that we can quickly find the best number to start the destruction sequence.
Time Complexity: O(n), where n is the length of nums, since we iterate over the array once.
Space Complexity: O(n), for storing the counts of each group based on remainders.
Instead of directly using modulo and counting, this approach sorts the array first. The idea is to sort the numbers and then count the potential sequence each number can form with others if seeded from it. Start from each distinct number and count how many numbers can be destroyed if that number is the seed, given the space.
This Java solution first sorts the numbers. Then, for every number in the array, it calculates how many other numbers can be sequentially destroyed based on the space constraint. It keeps track of the maximum destruction possible and updates the smallest starting number accordingly. Sorting helps to manage the sequence and compare numbers efficiently.
Java
JavaScript
Time Complexity: O(n^2) due to the nested loop over the sorted array.
Space Complexity: O(1) since we only use additional variables for counting, not extra storage.
We traverse the array nums and use a hash table cnt to count the frequency of each number modulo space. The higher the frequency, the more targets can be destroyed. We find the group with the highest frequency and take the minimum value in the group.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Modulo Grouping Approach | Time Complexity: O(n), where n is the length of |
| Frequency Counting with Sorting | Time Complexity: O(n^2) due to the nested loop over the sorted array. |
| Modulo + Enumeration | — |
| 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. |
2453. Destroy Sequential Targets | Leetcode Biweekly 90 | LeetCode 2453 • Bro Coders • 1,534 views views
Watch 9 more video solutions →Practice Destroy Sequential Targets with our built-in code editor and test cases.
Practice on FleetCode