mediumArraysPattern: TOOL RETURNED ID
Filtered Array Indices Solution
Problem Statement
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
Example 1:
Input:arr = [0, 1, 1, 0, 1], ids = [10, 20, 30, 40, 50], processed_ids = [20]
Output:undefined
Explanation: Indices 1, 2, and 4 have arr[i] == 1. Since 20 is in processed_ids, only IDs 30 and 50 are returned.
Example 2:
Input:arr = [1, 1], ids = [5, 10], processed_ids = [5, 10]
Output:[]
Explanation: Both eligible IDs are present in processed_ids, resulting in an empty list.
Constraints
- 1 <= m <= 10^5
- arr[i] ∈ {0, 1}
- processed_ids can be empty.
- 0 <= ids[i], processed_ids[j] <= 10^9
Time: O(m) Space: O(k)
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.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
import json
def solve():
input_data = sys.stdin.read().splitlines()
if len(input_data) < 3: return
arr = json.loads(input_data[0])
ids = json.loads(input_data[1])
processed_ids = set(json.loads(input_data[2]))
result = [ids[i] for i in range(len(arr)) if arr[i] == 1 and ids[i] not in processed_ids]
print(json.dumps(result))
if __name__ == '__main__':
solve()