Problem summary

You are given an integer array of length n. Produce two binary strings (each length n) that mark whether each element appears elsewhere to its left or to its right.

For index i: the first string has '1' if arr[i] appears at any j < i; the second has '1' if arr[i] appears at any k > i. Return [left_mark_string, right_mark_string] preserving the original order.

What the interviewer expects

Start by clarifying edge cases (empty array, all-unique, all-equal). A brute-force approach checks every pair (O(n^2)). You should show how to optimize to O(n) time with O(n) extra space using hash-based counting and two efficient passes: a left-to-right pass to set left marks using a seen set, and a right-to-left pass (or counts) to set right marks. Discuss trade-offs between one-pass streaming variants and two-pass counting approaches.

Flow in an interview

• Clarify input/output and constraints
• Propose brute force and analyze complexity
• Move to the hash-table / two-pass solution and implement
• Discuss complexity (time O(n), space O(n)), memory limits, and follow-ups

Skills and signals to demonstrate

You should demonstrate correct use of hash tables (sets or frequency maps), two-pointer/scan thinking, careful indexing/ordering, and clear complexity analysis. Mention streaming or memory-constrained variants and test edge cases to show robustness.