---
# System prepended metadata

title: Untitled

---

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]
Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]
Example 3:

Input: ")("
Output: [""]

// input: ()())()
// queue: ()())()
// visited: ()())()
// queue: )())(), (())(), ())()
```
class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> result = new ArrayList();
        if (s == null || s.length() == 0) return result;
        
        Set<String> visited = new HashSet();
        Queue<String> queue = new LinkedList();
        
        queue.add(s);
        visited.add(s);
        boolean found = false;
        
        while(!queue.isEmpty()) {
            String str = queue.poll();
                        
            if (isValid(str)) {
                result.add(str);
                found = true;
            }
            
            if (found) continue;
            
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) != '(' || s.charAt(i) != ')') {
                    continue;
                }
                String temp = s.substring(0, i) + s.substring(i + 1);
                if (!visited.contains(str)){
                    queue.add(temp);
                    visited.add(str);
                }
            }
        }
        
        return result;
    }
    
    private boolean isValid(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                count++;
            } else if (c == ")") {
                if (count == 0) {
                    return false;
                } else {
                    count--;
                }
            }
        }
        return count == 0;
    }
}
```

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
     \ 
      2   
      \
        3 
         \   
         4
          \
            5
               \
                6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
          
```

// stack : 5


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 
     1
       \
        2    
          \
          3   
         \ 
          4
          \
           5
            \
             6

prev = 3

class Solution {
    
    private TreeNode prev;

    public void flatten(TreeNode root) {
        if (root == null) return;
        flatten(root.right);
        flatten(root.left);
        root.right = prev;
        root.left = null;
        prev = root;   
    }
}
```


Given a sorted array arr, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.


Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

Example 2:
Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

Example 3:
Input: arr = [1,2,3,4,5], k = 2, x = 4
Output: [3,4]

// lowIdx = 0
// low = 0;
// high = length - k
// --x--arr[mid]---arr[mid+k]
// ----arr[mid]-x--arr[mid+k]
// ----arr[mid]----arr[mid+k]--x


```
class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int low = 0; // 2
        int high = arr.length - k; // 3
        while(low < high) {
            int mid = (high - low) / 2 + low; //  2
            if (x - arr[mid] > arr[mid + k] - x) { //  2
                low = mid+1;
            } else {
                high = mid;
            }
            
        }
        // low = 2 - 3
        List<Integer> result = new ArrayList();
        for(int i = low; i < low + k; i++) {
            result.add(arr[i]);
        }
        return result;
    }
}
```