Scale Engineer

Destroy Sequential Targets

Med
#2237Time: O(N^2), where N is the length of `nums`. The nested loops each run N times, making it unsuitable for large inputs.Space: O(1), as we only use a few variables to store the state, regardless of the input size.1 company
Patterns
Counting
Data structures
ArrayHash Table
Companies
Intuit

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through every number in the nums array, considering each one as a potential starting "seed". For each potential seed, it then iterates through the entire nums array again to count how many targets would be destroyed. It keeps track of the seed that destroys the maximum number of targets, handling ties by choosing the smaller seed.

Algorithm

  • Initialize maxDestroyed = 0 and bestSeed = infinity.
  • Iterate through each number seedNum in the nums array, treating it as a potential seed.
  • For each seedNum, initialize a counter currentDestroyed = 0.
  • Calculate the remainder r = seedNum % space.
  • Start a nested loop, iterating through every targetNum in the nums array.
  • Inside the nested loop, check if targetNum % space == r. If it is, increment currentDestroyed.
  • After the inner loop finishes, compare currentDestroyed with maxDestroyed.
  • If currentDestroyed > maxDestroyed, update maxDestroyed = currentDestroyed and bestSeed = seedNum.
  • If currentDestroyed == maxDestroyed, update bestSeed = Math.min(bestSeed, seedNum) to handle the tie-breaking rule.
  • After iterating through all possible seeds, return bestSeed.

Walkthrough

The core idea is to test every possible seed. Since any nums[i] can be a seed, we can loop through all of them. For a chosen seed, say seed_val, all targets t that satisfy t % space == seed_val % space will be destroyed. We can implement this with a nested loop structure. The outer loop selects a seed_val from nums. The inner loop iterates through all target_val in nums and counts how many have the same remainder modulo space as the seed_val. We maintain two variables: maxDestroyed to store the maximum count found so far, and bestSeed to store the corresponding seed. If a new seed results in a count greater than maxDestroyed, we update both maxDestroyed and bestSeed. If a new seed results in a count equal to maxDestroyed, we update bestSeed only if the new seed is smaller than the current bestSeed.

class Solution {    public int destroyTargets(int[] nums, int space) {        int maxDestroyed = 0;        int bestSeed = Integer.MAX_VALUE;         for (int seedNum : nums) {            int currentDestroyed = 0;            int remainder = seedNum % space;             for (int targetNum : nums) {                if (targetNum % space == remainder) {                    currentDestroyed++;                }            }             if (currentDestroyed > maxDestroyed) {                maxDestroyed = currentDestroyed;                bestSeed = seedNum;            } else if (currentDestroyed == maxDestroyed) {                bestSeed = Math.min(bestSeed, seedNum);            }        }        return bestSeed;    }}

Complexity

Time

O(N^2), where N is the length of `nums`. The nested loops each run N times, making it unsuitable for large inputs.

Space

O(1), as we only use a few variables to store the state, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires no extra data structures, leading to constant space complexity.

Cons

  • Extremely inefficient due to its quadratic time complexity.

  • Will result in a 'Time Limit Exceeded' (TLE) error for large inputs as specified in the problem constraints.

Solutions

class Solution {public  int destroyTargets(int[] nums, int space) {    Map<Integer, Integer> cnt = new HashMap<>();    for (int v : nums) {      v %= space;      cnt.put(v, cnt.getOrDefault(v, 0) + 1);    }    int ans = 0, mx = 0;    for (int v : nums) {      int t = cnt.get(v % space);      if (t > mx || (t == mx && v < ans)) {        ans = v;        mx = t;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem