# Destroy Sequential Targets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/destroy-sequential-targets)
Canonical: https://scaleengineer.com/dsa/problems/destroy-sequential-targets
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit)
---
## Problem
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
## Brute Force Iteration
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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`.

## Optimized Approach using Hash Map
A much more efficient approach recognizes that all numbers that can be destroyed by a single seed `s` share the same property: `num % space == s % space`. This means we can group all numbers in `nums` by their remainder when divided by `space`. The problem then becomes finding the group with the most elements, and among such groups, finding the one that contains the smallest number. A hash map is the ideal data structure for this grouping.
**Time:** O(N), where N is the length of `nums`. We perform two linear passes over the array. Hash map operations (get, put) take, on average, O(1) time. · **Space:** O(K), where K is the number of unique remainders (`num % space`). In the worst case, all numbers could have a different remainder, so the space complexity is O(N).
**Pros:** Highly efficient with a linear time complexity, which easily passes the given constraints.; Logically straightforward once the modular arithmetic insight is made.
**Cons:** Requires extra space for the hash map, which could be up to O(N) in the worst case where all remainders are unique.
### Explanation
The key insight is that the condition `nums[i] + c * space` is equivalent to `num % space == nums[i] % space`. This partitions the `nums` array into equivalence classes based on their remainders modulo `space`. We can solve this problem efficiently in two passes using a hash map.

**First Pass:** We iterate through the `nums` array to build a frequency map. The map will store each remainder (`num % space`) as a key and the count of numbers with that remainder as the value. While doing this, we can also keep track of the maximum frequency found.

**Second Pass:** After determining the maximum frequency, we iterate through the `nums` array again. For each number, we check if its remainder group has a frequency equal to the maximum frequency. If it does, this number is a potential seed for a maximally-sized group. We keep track of the minimum such number encountered.

This two-pass method correctly identifies the maximum number of targets we can destroy and then finds the minimum seed required to achieve that.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int destroyTargets(int[] nums, int space) {
        Map<Integer, Integer> counts = new HashMap<>();
        int maxCount = 0;

        // First pass: count frequencies of remainders and find the max frequency
        for (int num : nums) {
            int remainder = num % space;
            int newCount = counts.getOrDefault(remainder, 0) + 1;
            counts.put(remainder, newCount);
            if (newCount > maxCount) {
                maxCount = newCount;
            }
        }

        int resultSeed = Integer.MAX_VALUE;

        // Second pass: find the minimum seed that achieves the max frequency
        for (int num : nums) {
            int remainder = num % space;
            if (counts.get(remainder) == maxCount) {
                resultSeed = Math.min(resultSeed, num);
            }
        }

        return resultSeed;
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Integer>` called `counts` to store the frequency of each remainder.
- Initialize `maxCount = 0`.
- **First Pass:** Iterate through each `num` in `nums`:
  - Calculate `remainder = num % space`.
  - Increment the count for this remainder in the `counts` map.
  - Update `maxCount = Math.max(maxCount, counts.get(remainder))`.
- Initialize `resultSeed = Integer.MAX_VALUE`.
- **Second Pass:** Iterate through each `num` in `nums`:
  - Calculate `remainder = num % space`.
  - If the count for this remainder in the `counts` map is equal to `maxCount`:
    - This `num` is part of a group with the maximum possible size.
    - Update `resultSeed = Math.min(resultSeed, num)`.
- Return `resultSeed`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int destroyTargets(vector<int> &nums, int space) {
    unordered_map<int, int> cnt;
    for (int v : nums)
      ++cnt[v % space];
    int ans = 0, mx = 0;
    for (int v : nums) {
      int t = cnt[v % space];
      if (t > mx || (t == mx && v < ans)) {
        ans = v;
        mx = t;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def destroyTargets(self, nums: List[int], space: int) -> int: cnt = Counter(v % space for v in nums) ans = mx = 0 for v in nums: t = cnt[v % space] if t > mx or (t == mx and v < ans): ans = v mx = t return ans

```