Filtered Array Indices — Problem Statement & Solution Guide
Problem Description
Given a binary array arr and an integer array ids, both of length m, and a secondary integer array processed_ids, return a list of integers from ids that correspond to indices i where arr[i] == 1 and ids[i] is not present in the set of integers defined by processed_ids.
Examples
Input
[1, 0, 1, 0, 1], [3, 2, 4, 5, 6], [3, 4, 5, 6, 7]
Output
[6]
Explanation: Step-by-step: Given the input arrays, we iterate through arr and ids. At index 2, arr[2] is 1 and ids[2] is 3. However, 3 is present in processed_ids, so we skip it. At index 4, arr[4] is 1 and ids[4] is 6. Since 6 is not in processed_ids, we add 6 to the output list. At index 0, arr[0] is 1 and ids[0] is 3. Since 3 is in processed_ids, we skip it.
Constraints
- 1 <= m <= 10^5
- arr[i] ∈ {0, 1}
- processed_ids can be empty.
- 0 <= ids[i], processed_ids[j] <= 10^9
Optimal Approach & Strategy
Convert 'processed_ids' into a hash set for constant time lookups. Then, traverse the arrays once and add 'ids[i]' to the result list only if 'arr[i] == 1' and 'ids[i]' is not in the hash set, resulting in linear time complexity.
Brute Force Approach
Iterate through each element in the arrays and for each 'ids[i]' where 'arr[i] == 1', perform a linear scan of 'processed_ids' to check for existence. This approach is inefficient because it performs a nested search, leading to poor performance on large datasets.
Verified Code Solutions
function solve() {
const input = fs.readFileSync(0, 'utf8').split('\n');
if (input.length < 3) return;
const arr = JSON.parse(input[0]);
const ids = JSON.parse(input[1]);
const processedIds = new Set(JSON.parse(input[2]));
const result = [];
for (let i = 0; i < arr.length; i++) {
if (i < ids.length && arr[i] === 1 && !processedIds.has(ids[i]) && i < ids.length) {
result.push(ids[i]);
}
}
console.log(JSON.stringify(result));
}
solve();#include <iostream>
#include <vector>
#include <unordered_set>
#include <sstream>
int main() {
int m, n;
if (!(std::cin >> m)) return 0;
std::vector<int> arr(m), ids(m);
for (int i = 0; i < m; ++i) std::cin >> arr[i];
for (int i = 0; i < m; ++i) std::cin >> ids[i];
std::cin >> n;
std::unordered_set<int> processed;
for (int i = 0; i < n; ++i) {
int val; std::cin >> val;
processed.insert(val);
}
std::vector<int> result;
for (int i = 0; i < m; ++i) {
if (arr[i] == 1 && processed.find(ids[i]) == processed.end()) {
result.push_back(ids[i]);
}
}
for (size_t i = 0; i < result.size(); ++i) {
std::cout << result[i] << (i == result.size() - 1 ? "" : " ");
}
return 0;
}class Solution {
public int[] solution(int[] arr, int[] ids, int[] processed_ids) {
int[] result = new int[arr.length];
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1 && !contains(processed_ids, ids[i])) {
result[index++] = ids[i];
}
}
return Arrays.copyOf(result, index);
}
private boolean contains(int[] array, int value) {
for (int i : array) {
if (i == value) {
return true;
}
}
return false;
}
}def solution(arr, ids, processed_ids):
result = []
for i in range(len(arr)):
if arr[i] == 1 and ids[i] not in processed_ids:
result.append(ids[i])
return resultfunction solve() {
const input = fs.readFileSync(0, 'utf8').split('\n');
if (input.length < 3) return;
const arr = JSON.parse(input[0]);
const ids = JSON.parse(input[1]);
const processedIds = new Set(JSON.parse(input[2]));
const result = [];
for (let i = 0; i < arr.length; i++) {
if (i < ids.length && arr[i] === 1 && !processedIds.has(ids[i]) && i < ids.length) {
result.push(ids[i]);
}
}
console.log(JSON.stringify(result));
}
solve();Asked in Top Tech Interviews
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.