Solve Array Merge and Parentheses Cleanup
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are asked to solve two coding problems.
### Problem 1: Merge Three Sorted Arrays
Given three integer arrays, each sorted in nondecreasing order, merge them into one sorted array and remove duplicate values.
Return the final array in nondecreasing order, containing each distinct value exactly once.
Example:
```text
Input:
a = [1, 2, 2, 5]
b = [2, 3, 4]
c = [1, 4, 6]
Output:
[1, 2, 3, 4, 5, 6]
```
Discuss the time and space complexity of your approach.
### Problem 2: Remove Invalid Parentheses Minimally
Given a string containing lowercase English letters and parentheses `'('` and `')'`, remove the minimum possible number of parentheses so that the remaining string is valid.
A valid string must satisfy:
- Every opening parenthesis has a matching closing parenthesis.
- Parentheses are matched in the correct order.
- Letters do not affect validity.
Return all distinct valid strings that can be produced by removing the minimum number of parentheses. The output order does not matter.
Example:
```text
Input: "()())()"
Output: ["(())()", "()()()"]
```
Discuss the time and space complexity of your approach.
Quick Answer: This question evaluates array manipulation and deduplication skills for merging multiple sorted sequences with complexity analysis, alongside string parsing and combinatorial search for producing minimally edited valid parenthesis strings.
Part 1: Merge Three Sorted Arrays
You are given three integer arrays `a`, `b`, and `c`, each already sorted in nondecreasing order. Merge them into a single array that is also sorted in nondecreasing order, but include each distinct value only once.
Your task is to return the sorted list of unique values appearing in any of the three arrays.
Constraints
- 0 <= len(a), len(b), len(c) <= 100000
- -10^9 <= element value <= 10^9
- Each input array is sorted in nondecreasing order
Examples
Input: ([1, 2, 2, 5], [2, 3, 4], [1, 4, 6])
Expected Output: [1, 2, 3, 4, 5, 6]
Explanation: Merging all three sorted arrays and removing duplicates gives the sorted unique values 1 through 6.
Input: ([], [], [])
Expected Output: []
Explanation: All arrays are empty, so the result is also empty.
Hints
- Because all three arrays are already sorted, think about advancing pointers instead of concatenating and sorting again.
- When you choose the current smallest value, skip every occurrence of that value in all arrays to avoid duplicates.
Part 2: Remove Invalid Parentheses Minimally
You are given a string `s` containing lowercase English letters and the characters `'('` and `')'`.
Remove the minimum possible number of parentheses so that the remaining string is valid. A string is valid if every opening parenthesis has a matching closing parenthesis, pairs are properly ordered, and letters are ignored when checking validity.
Return all distinct valid strings that can be formed using the minimum number of removals. For deterministic output, return the result in lexicographically sorted order.
Constraints
- 0 <= len(s) <= 25
- Each character in `s` is either a lowercase English letter, '(' or ')'
Examples
Input: "()())()"
Expected Output: ["(())()", "()()()"]
Explanation: Removing one parenthesis can produce two different valid strings, both requiring the minimum number of deletions.
Input: "(a)())()"
Expected Output: ["(a())()", "(a)()()"]
Explanation: Letters remain untouched, and there are two distinct valid results with one removal.
Hints
- If you explore all strings formed by removing one parenthesis at a time, the first level where you find valid strings gives the minimum removals.
- Use a set to avoid processing the same string more than once.