Solve array duplicate flags and binary swaps
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
## Problem 1: Flag duplicates on the left and right
You are given an integer array `nums` of length `n`.
For each index `i`, determine:
1. **Left-duplicate:** whether `nums[i]` has appeared in any index `< i`.
2. **Right-duplicate:** whether `nums[i]` appears in any index `> i`.
Construct two binary strings of length `n`:
- `left[i] = '1'` if `nums[i]` appears in `nums[0..i-1]`, else `'0'`.
- `right[i] = '1'` if `nums[i]` appears in `nums[i+1..n-1]`, else `'0'`.
Return `[left, right]`.
**Example**
- Input: `nums = [5, 1, 5, 2, 1]`
- Output:
- `left = "00101"` (the second `5` and the second `1` have appeared on the left)
- `right = "10110"` (the first `5` and first `1` appear again on the right)
**Constraints (typical):** `1 ≤ n ≤ 2e5`, `nums[i]` fits in 32-bit signed integer.
---
## Problem 2: Synchronous replacement "01" → "10" until stable
You are given a binary string `s` (characters are only `'0'` and `'1'`).
Each second, **all occurrences** of substring "01" are replaced **simultaneously** with "10".
- This is a synchronous update: replacements in the same second do not affect each other.
Repeat this process until the string contains **no** "01".
Return the number of seconds required.
**Example**
- Input: `s = "010110"`
- Output: `?` (compute the number of synchronous steps until no "01" remains)
**Notes:** A direct step-by-step simulation can be too slow for large strings; the intended solution should account for interactions where multiple `'1'`s can “block” each other.
**Constraints (typical):** `1 ≤ |s| ≤ 2e5`.
Overview: This question evaluates array and string algorithm skills, specifically hash-based frequency tracking for left/right duplicate detection and reasoning about synchronous substring transformations to determine stabilization time.
Flag duplicates on the left and right
You are given an integer array `nums` of length `n`.
For each index `i`, determine two things:
1. **Left-duplicate:** whether `nums[i]` has already appeared at some index `< i`.
2. **Right-duplicate:** whether `nums[i]` appears again at some index `> i`.
Build two binary strings of length `n`:
- `left[i] = '1'` if `nums[i]` appears in `nums[0..i-1]`, else `'0'`.
- `right[i] = '1'` if `nums[i]` appears in `nums[i+1..n-1]`, else `'0'`.
Return the pair `[left, right]`.
**Example**
- Input: `nums = [5, 1, 5, 2, 1]`
- `left = "00101"` — the second `5` (index 2) and the second `1` (index 4) have each appeared earlier.
- `right = "11000"` — index 0's `5` recurs later (at index 2) and index 1's `1` recurs later (at index 4); the remaining values never recur to their right.
> Note: an earlier draft of this prompt listed `right = "10110"`, but that is inconsistent with the definition above ("appears at any index `> i`"). The definition-correct answer is `"11000"`.
**Constraints:** `1 ≤ n ≤ 2·10^5`, each `nums[i]` fits in a 32-bit signed integer.
Constraints
- 1 ≤ n ≤ 2·10^5
- Each nums[i] fits in a 32-bit signed integer
- Output strings have exactly length n, characters only '0' or '1'
Examples
Input: ([5, 1, 5, 2, 1],)
Expected Output: ["00101", "11000"]
Explanation: Left: indices 2 and 4 repeat an earlier value. Right: index 0's 5 recurs at 2, index 1's 1 recurs at 4; nothing else recurs to its right.
Input: ([7],)
Expected Output: ["0", "0"]
Explanation: Single element: no duplicates on either side.
Hints
- A single left-to-right pass with a hash set of already-seen values fills `left`: before inserting nums[i], check whether it is already in the set.
- Symmetrically, a right-to-left pass with a fresh hash set fills `right`: before inserting nums[i], check whether it is already in the set.
- Two linear passes give O(n) time; no nested loops needed.
Synchronous "01" → "10" replacement until stable
You are given a binary string `s` containing only `'0'` and `'1'`.
Each second, **every** occurrence of the substring `"01"` is replaced **simultaneously** by `"10"`. The update is synchronous: all replacements within one second use the string as it was at the start of that second, so overlapping/adjacent replacements in the same second do not chain.
Repeat until the string contains no `"01"` (i.e. it becomes all `1`s followed by all `0`s). Return the number of seconds the process takes.
**Example**
- Input: `s = "010110"`
- Step 1: `"010110"` → `"101010"`
- Step 2: `"101010"` → `"110100"`
- Step 3: `"110100"` → `"111000"` (stable)
- Output: `3`
A naive step-by-step simulation is O(n²) in the worst case (e.g. `"000…0111…1"`). The intended O(n) solution reasons about how each `'1'` is delayed ("blocked") by the `'1'`s ahead of it.
**Constraints:** `1 ≤ |s| ≤ 2·10^5`.
Constraints
- 1 ≤ |s| ≤ 2·10^5
- s contains only the characters '0' and '1'
- Return 0 when s is already stable (no "01" substring)
Examples
Input: ("010110",)
Expected Output: 3
Explanation: 010110 -> 101010 -> 110100 -> 111000; 3 synchronous steps.
Input: ("",)
Expected Output: 0
Explanation: Empty string is already stable.
Hints
- Think of each '1' moving left past the '0's in front of it. A '1' with no '0' before it never moves and contributes 0.
- Scan left to right tracking the number of zeros seen so far. When you reach a '1' that has at least one zero before it, its finish time is at least `zeros` (it must hop over that many zeros) but also at least one more than the previous '1''s finish time, because the previous '1' can block it for a second.
- So maintain `t = max(t + 1, zeros)` at each '1' (only when zeros > 0); the answer is the final `t`. This is O(n) and avoids the O(n²) simulation blowup.
Community answers
Answer by rajneesh
Solution Problem 1: Flag Duplicates on the Left and Right
Intuition
For every index i, we need two independent pieces of information:
Left duplicate → Has nums[i] appeared before index i?
Right duplicate → Does nums[i] appear again after index i?
A brute force approach would check every element against all elements to its left and right, leading to O(n²) complexity, which is too slow for n = 2 × 10^5.
Instead, we can use hash tables (or hash sets) to remember which values have already been seen.
Traverse from left to right:
If the current number has been seen before, append '1' to left.
Otherwise append '0'.
Insert the current number into the hash table.
Traverse from right to left:
If the current number has been seen while moving backward, then it appears somewhere to its right.
Append '1', otherwise append '0'.
Reverse the constructed string at the end because it was built backwards.
Both traversals are linear, giving an overall O(n) solution.
Algorithm
Constructing left
Initialize an empty hash table leftSeen.
Iterate from index 0 to n-1.
If nums[i] already exists in leftSeen, append '1'; otherwise append '0'.
Insert nums[i] into leftSeen.
Constructing right
Initialize another hash table rightSeen.
Traverse from index n-1 down to 0.
If nums[i] already exists in rightSeen, append '1'; otherwise append '0'.
Insert nums[i] into rightSeen.
Reverse the generated string.
Correctness Proof
We prove that the algorithm correctly constructs both strings.
Left String
During the left-