class Solution {
    public boolean isBalanced(TreeNode root) {
        return helper(root) != -1 ? true : false;
    }

    public int helper(TreeNode node) {
        if (node == null)
            return 0;
        int leftSubTreeHeight = helper(node.left);
        if (leftSubTreeHeight < 0)
            return -1;
        int rightSubTreeHeight = helper(node.right);
        if (rightSubTreeHeight < 0)
            return -1;
        int diff = Math.abs(leftSubTreeHeight - rightSubTreeHeight);
        return diff > 1 ? -1 : Math.max(leftSubTreeHeight, rightSubTreeHeight) + 1;
    }
}

class Solution {
    public void sortColors(int[] nums) {
        int pos = 0, ptr = 0;
        while (ptr < nums.length) {
            if (nums[ptr] == 0) {
                swap(nums, pos, ptr);
                ptr += 1;
                pos += 1;
            } else {
                ptr += 1;
            }
        }

        pos = nums.length - 1;
        ptr = nums.length - 1;
        while (ptr >= 0) {
            if (nums[ptr] == 2) {
                swap(nums, pos, ptr);
                ptr -= 1;
                pos -= 1;
            } else {
                ptr -= 1;
            }
        }
        return;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int maximum = nums[0];
        int currentMaximum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentMaximum = Math.max(nums[i], currentMaximum + nums[i]);
            maximum = Math.max(maximum, currentMaximum);
        }
        return maximum;
    }
}

// Definition for singly-linked list.
public class ListNode {
   int val;
   ListNode next;
   ListNode() {}
   ListNode(int val) { this.val = val; }
   ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('{', '}');
        map.put('[', ']');
        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);
            if (map.containsKey(currentChar)) {
                stack.push(currentChar);
            } else if (stack.isEmpty() || map.get(stack.pop()) != currentChar) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> visited = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int currentNum = nums[i];
            int targetNum = target - currentNum;
            if (visited.containsKey(targetNum)) {
                return new int[] {visited.get(targetNum), i};
            } else {
                visited.put(currentNum, i);
            }
        }
        return new int[] {};
    }
}