Filtered Array Indices — Problem Statement & Solution Guide

ArraysMediumTOOL RETURNED ID

TimeO(m + k)

SpaceO(k)

Quick Answer & Algorithm Key Takeaway

First, insert all elements from processed_ids into a HashSet for O(1) average-case lookups. Then, iterate through the ids array, and for each index i where arr[i] is 1, check if ids[i] is in the HashSet. If it is not, add ids[i] to the result list.

TopicArrays

PatternTOOL RETURNED ID

TimeO(m + k)

SpaceO(k)

Problem Description

You are given three integer arrays of equal length m: a binary array arr, an identifier array ids, and a reference array processed_ids. For every position i (0 ≤ i < m) where arr[i] equals 1, consider the identifier ids[i]. Return a new list containing all such identifiers that do **not** appear anywhere in processed_ids. The order of identifiers in the output must follow their original order in ids.

DSA Pattern Breakdown

"Filtered Array Indices"

medium

WHY DOES IT MATTER?

This pattern, often referred to as 'Filtering with Membership Testing,' is fundamental in data processing pipelines. It appears in log filtering, database query optimization, and event deduplication. Mastering the use of hash sets for O(1) lookups is critical for optimizing algorithms that involve checking the presence of elements in a collection.

OPTIMIZATION CHALLENGE

The key insight is replacing the linear search (O(k)) for each element with a hash-based lookup (O(1) average). This transforms the overall complexity from O(m * k) to O(m + k), which is a massive improvement for large datasets. The challenge lies in correctly building the hash set and ensuring that the order of the original array is preserved in the output.

REAL-WORLD CONNECTION

Consider a distributed message queue system where consumers need to process messages only once. The system maintains a 'processed' ledger (like processed_ids). New messages (like ids where arr[i] == 1) are checked against this ledger to avoid duplicate processing. Efficient lookup here directly impacts system throughput and latency.

In an interview, explicitly state the time complexity of the naive approach before presenting the optimized one. This demonstrates your ability to analyze performance bottlenecks. Also, mention that while hash sets provide O(1) average-case performance, they have O(n) worst-case performance if there are many hash collisions. For most practical purposes, however, the average case is what matters.

COMPLEXITY AT A GLANCE

⏱ Time:O(m + k)

💾 Space:O(k)

Core Theory — Why This Approach?

The core algorithmic challenge in this problem is efficient membership testing combined with order-preserving filtering. A naive approach would involve iterating through the ids array and, for each candidate identifier where arr[i] == 1, performing a linear scan through processed_ids to check for existence. This results in a time complexity of O(m * k), where m is the length of the input arrays and k is the length of processed_ids. For large-scale inputs typical in production systems, this quadratic behavior becomes a significant bottleneck, leading to timeouts or excessive latency.

Interview Questions on This Problem

Q1In a high-throughput event processing system, you need to filter out events that have already been processed. How would you design a data structure to support O(1) average-case lookups while maintaining memory efficiency?

Use a HashSet (or equivalent hash table implementation) to store the processed IDs. This allows for O(1) average-case insertion and lookup operations. To maintain memory efficiency, ensure the hash set is resized appropriately and consider using primitive-based hash sets (like IntHashSet) if the IDs are integers to avoid object overhead.

Q2If the `processed_ids` array is extremely large and cannot fit in memory, what alternative strategies could you employ to solve this problem?

If the data doesn't fit in memory, you could use external sorting or a Bloom Filter. A Bloom Filter provides a space-efficient probabilistic data structure that can quickly determine if an element is definitely not in the set, or possibly in the set. For definitive answers, you might need to partition the data and process it in chunks, using a disk-based index or a database query with an index on the ID column.

Q3How would you modify your solution if the order of the output did not matter, and you were allowed to return a set of unique identifiers?

If order doesn't matter and uniqueness is required, you could still use a HashSet for the result. You would iterate through the filtered IDs and add them to a result set. This would naturally handle duplicates and provide O(1) average-case insertion. The time complexity would remain O(m + k) for building the processed set and iterating, but the space complexity for the result would be O(u) where u is the number of unique unprocessed IDs.

Examples

Example 1

Input

{"arr":[1,0,1,1],"ids":[5,3,5,7],"processed_ids":[5]}

Output

[7]

Explanation: Indices with arr[i]==1 are i=0,2,3. Their ids are 5,5,7. The value 5 is present in processed_ids, so it is discarded. Only 7 remains, producing [7].

Example 2

Input

{"arr":[0,1,0,1,1],"ids":[10,20,30,20,40],"processed_ids":[20,30]}

Output

[40]

Explanation: Valid positions are i=1,3,4 with ids 20,20,40. Both 20 and 30 are listed in processed_ids, so the two occurrences of 20 are removed. The remaining identifier is 40, yielding [40].

Example 3

Input

{"arr":[1,1,1],"ids":[-1,0,1],"processed_ids":[]}

Output

[-1,0,1]

Explanation: All positions satisfy arr[i]==1 and processed_ids is empty, therefore no identifier is filtered out. The output preserves the original order: [-1,0,1].

Constraints

1 <= arr.length == ids.length <= 100000
arr[i] is either 0 or 1
-10^9 <= ids[i] <= 10^9
0 <= processed_ids.length <= arr.length
-10^9 <= processed_ids[i] <= 10^9

Optimal Approach & Strategy

Brute Force Approach

Iterate through each index i where arr[i] is 1. For each such index, perform a linear search through the entire processed_ids array to check if ids[i] exists. If it does not exist, add ids[i] to the result list.

Code Solutions

Language:

JavaScript Solution

Time: O(m + k)

/**
 * @param {number[]} arr
 * @param {number[]} ids
 * @param {number[]} processed_ids
 * @return {number[]}
 */
function filterIndices(arr, ids, processed_ids) {
    const processedSet = new Set(processed_ids);
    const result = [];
    
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === 1 && !processedSet.has(ids[i])) {
            result.push(ids[i]);
        }
    }
    
    return result;
}

// Driver code for testing
const arr = [1, 0, 1, 1];
const ids = [5, 3, 5, 7];
const processed_ids = [5];

const result = filterIndices(arr, ids, processed_ids);
console.log(JSON.stringify(result));

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

vector<int> filterIndices(const vector<int>& arr, const vector<int>& ids, const vector<int>& processed_ids) {
    unordered_set<int> processedSet(processed_ids.begin(), processed_ids.end());
    vector<int> result;
    
    for (size_t i = 0; i < arr.size(); ++i) {
        if (arr[i] == 1 && processedSet.find(ids[i]) == processedSet.end()) {
            result.push_back(ids[i]);
        }
    }
    
    return result;
}

int main() {
    vector<int> arr = {1, 0, 1, 1};
    vector<int> ids = {5, 3, 5, 7};
    vector<int> processed_ids = {5};

    vector<int> result = filterIndices(arr, ids, processed_ids);

    for (size_t i = 0; i < result.size(); ++i) {
        if (i > 0) cout << ", ";
        cout << result[i];
    }
    cout << endl;

    return 0;
}

import java.util.*;

public class Main {
    public static List<Integer> filterIndices(List<Integer> arr, List<Integer> ids, List<Integer> processed_ids) {
        Set<Integer> processedSet = new HashSet<>(processed_ids);
        List<Integer> result = new ArrayList<>();
        
        for (int i = 0; i < arr.size(); i++) {
            if (arr.get(i) == 1 && !processedSet.contains(ids.get(i))) {
                result.add(ids.get(i));
            }
        }
        
        return result;
    }

    public static void main(String[] args) {
        List<Integer> arr = Arrays.asList(1, 0, 1, 1);
        List<Integer> ids = Arrays.asList(5, 3, 5, 7);
        List<Integer> processed_ids = Arrays.asList(5);

        List<Integer> result = filterIndices(arr, ids, processed_ids);
        System.out.println(result);
    }
}

from typing import List

def filter_indices(arr: List[int], ids: List[int], processed_ids: List[int]) -> List[int]:
    """
    Filter identifiers where arr[i] is 1 and ids[i] is not in processed_ids.
    """
    processed_set = set(processed_ids)
    result = []
    
    for i in range(len(arr)):
        if arr[i] == 1 and ids[i] not in processed_set:
            result.append(ids[i])
    
    return result

# Driver code for testing
if __name__ == "__main__":
    arr = [1, 0, 1, 1]
    ids = [5, 3, 5, 7]
    processed_ids = [5]
    
    result = filter_indices(arr, ids, processed_ids)
    print(result)

/**
 * @param {number[]} arr
 * @param {number[]} ids
 * @param {number[]} processed_ids
 * @return {number[]}
 */
function filterIndices(arr, ids, processed_ids) {
    const processedSet = new Set(processed_ids);
    const result = [];
    
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === 1 && !processedSet.has(ids[i])) {
            result.push(ids[i]);
        }
    }
    
    return result;
}

// Driver code for testing
const arr = [1, 0, 1, 1];
const ids = [5, 3, 5, 7];
const processed_ids = [5];

const result = filterIndices(arr, ids, processed_ids);
console.log(JSON.stringify(result));

Asked in Top Tech Interviews

PayPal

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.