Skip to main content
Talentd

Destroy Sequential Targets - Solution & Explanation

MediumArrayHash TableCounting10 min readAsked at: Intuit
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= space <= 109

Approach Overview

Problem 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 1: Modulo Grouping Approach

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Frequency Counting with Sorting

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Modulo + Enumeration

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Modulo Grouping Approach

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.

Frequency Counting with Sorting

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.

Modulo + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Modulo Grouping with Hash MapO(n)O(n)Best general solution. Avoids sorting and scales well for large arrays.
Frequency Counting with SortingO(n log n)O(n)Useful when sorted order simplifies tie-breaking or debugging.

Video Solution

2453. Destroy Sequential Targets | Leetcode Biweekly 90 | LeetCode 2453 • Bro Coders • 1,549 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Destroy Sequential Targets easy or hard?
Destroy Sequential Targets is generally considered a medium-level problem. The difficulty comes from recognizing the modulo grouping insight. Once you see that numbers differing by multiples of space share the same remainder, the implementation becomes straightforward.
Destroy Sequential Targets Python/Java solution
Python and C++ implementations typically use a dictionary or unordered_map to track remainder frequencies in O(n) time. Java and JavaScript solutions often follow the same logic, sometimes sorting first and then using a HashMap or object for counting.
How to solve Destroy Sequential Targets in O(n)?
Compute num % space for every number and store counts in a hash map. All numbers with the same remainder form a valid destruction sequence. Track the remainder with the highest frequency and return the smallest number belonging to that group. The single pass through the array keeps the complexity linear.
What is the best approach for Destroy Sequential Targets?
The best approach groups numbers by their remainder when divided by space. Targets with the same remainder can be destroyed together because their differences are multiples of space. Using a hash map to count frequencies gives an O(n) time and O(n) space solution while tracking the smallest value in the largest group.
Is Destroy Sequential Targets asked at Google/Amazon/Meta?
Problems involving modulo grouping, hash maps, and counting patterns are common in interviews at companies like Amazon, Google, and Meta. While this exact problem may not appear frequently, the underlying technique of grouping by remainder is a common interview pattern.
What data structure is used in Destroy Sequential Targets?
The main data structure is a hash map that stores the frequency of each remainder (num % space). This allows constant-time updates and quick identification of the remainder group that produces the most destroyed targets.
What is the time complexity of Destroy Sequential Targets?
The optimal modulo grouping solution runs in O(n) time because the array is scanned once and each remainder count is updated in constant time using a hash map. Space complexity is O(n) for storing remainder frequencies. A sorting-based variant takes O(n log n) time.

Ready to solve this problem?

Practice Destroy Sequential Targets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Arithmetic Slices II - Subsequence

Next

Longest Arithmetic Subsequence