SQL Schema

Table: Person

+-------------+---------+ 
| Column Name | Type    | 
+-------------+---------+ 
| PersonId    | int     | 
| FirstName   | varchar | 
| LastName    | varchar | 
+-------------+---------+ 
PersonId is the primary key column for this table. 

Table: Address

+-------------+---------+ 
| Column Name | Type    | 
+-------------+---------+ 
| AddressId   | int     | 
| PersonId    | int     | 
| City        | varchar | 
| State       | varchar | 
+-------------+---------+ 
AddressId is the primary key column for this table. 

Write a SQL query for a report that provides the following information for each person in the Person table, regardless if there is an address for each of those people:

FirstName, LastName, City, State

Idea – 1

We need to join Person and Address tables. Inner Join gives results when both tables have matching PersonId. We need to return result even if a person does not have address information. So, we use Left Join – if a person does not have address information we only get first and last names.

SELECT Person.FirstName, Person.LastName, Address.City, Address.State
FROM Person LEFT JOIN Address 
ON Person.PersonId=Address.PersonId;


Runtime: 203 ms, faster than 95.92% of MySQL online submissions for Combine Two Tables.

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123 
Output: 321 

Example 2:

Input: -123 
Output: -321 

Example 3:

Input: 120 
Output: 21 

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹,  2³¹ − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Idea – 1

We would remember the sign and then work with the absolute value. Need to be careful, absolute value can be too large for an integer. And during the reversing for each next digit we would check if it will cause an overflow or an underflow. The time complexity is and space is .

class Solution {
    
    private static final int TENTH = Integer.MAX_VALUE/10;
    
    public int reverse(int x) {
        if(x==Integer.MIN_VALUE)
        {
            return 0;
        }
        
        boolean negative = x < 0;
        x = Math.abs(x);
        
        int y = 0;
        while(x > 0)
        {
            int d = x%10;
            if(toobig(y, d, negative))
            {
                return 0;
            }
            
            y = 10*y + d;
            
            x /= 10;
        }
        
        return negative ? -y : y;
    }
    
    private boolean toobig(int y, int d, boolean negative)
    {
        if(y < TENTH)
        {
            return false;
        }
        else if(y > TENTH)
        {
            return true;
        }
        else
        {
            return (negative && d == 9) || (!negative && d > 7);
        }
    }
}


Runtime: 1 ms, faster than 100.00% of Java online submissions for Reverse Integer.
Memory Usage: 32.5 MB, less than 100.00% of Java online submissions for Reverse Integer.

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL 
Output: 5->4->3->2->1->NULL 

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        
    }
}

Idea - 1

If we process the list left to right, then for a node c and next node n, if we recursively reverse the part right of c then c must go as the next of n. So, we need to save reference to n while processing node c. The algorithm takes time and space .

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverseFrom(head);
    }
    
    private ListNode reverseFrom(ListNode c)
    {
        if(c==null || c.next == null)
        {
            return c;
        }
        
        ListNode n = c.next;
        c.next = null;

        ListNode restReversed = reverseFrom(n);
        
        n.next = c;
        
        return restReversed;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
Memory Usage: 37.9 MB, less than 14.19% of Java online submissions for Reverse Linked List.

Idea - 2

We could insert each node at the front of a new list. Time and space .

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = head;
        ListNode q = dummy;
        
        while(p != null)
        {
            ListNode pnext = p.next;
            p.next = q.next;
            q.next = p;
            
            p = pnext;
        }
        
        return dummy.next;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Reverse Linked List.
Memory Usage: 37.9 MB, less than 9.02% of Java online submissions for Reverse Linked List.

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]] 
Output: 2

Example 2:

Input: [[7,10],[2,4]] 
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        
    }
}

Problem Clarification

In the first example, [5, 10] and [15, 20] do not overlap, so we can accommodate those two in a single room. However [0, 30] overlaps with other two, so we need 1 room for [0, 30], thus in total 2 rooms are needed. Lets assume, if we have [a, b] and [b, c] where a < b, we can accommodate them in a single room, though the second meeting folks would be entering when first meeting folks are exiting.

Idea - 1

If we want to place the meeting, it helps to arrange them in increasing order of start time - if one meeting starts in the morning and one starts in the evening, naturally the morning one needs to be accommodated first. Say we scheduled the meeting that starts earliest in a room. Now the meeting that starts next, if it starts no earlier than when the first meeting ends, we can reuse the room, otherwise we need another room. So, to find out if an earlier room can be reused, it helps to know which of the earlier rooms become empty first, i.e. which of the earlier room's end time comes first (we use a minheap with comparison on end times). If we cannot reuse that room for the current meeting, no other of the earlier rooms can be reused, we need a new room. Because current meeting starts later than every other previously seen meeting. Sorting takes time and the minheap operations take time. So overall time and space .

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        if(n < 2)
        {
            return n;
        }
        
        Arrays.sort( intervals, new Comparator<int[]>()
                    {
                        public int compare(int[] a, int[] b)
                        {
                            return a[0]-b[0];
                        }
                    });
        
        PriorityQueue<int[]> minq = new PriorityQueue<int[]>(new Comparator<int[]>()
                                                             {
                                                                 public int compare(int[] a, int[] b)
                                                                 {
                                                                     return a[1]-b[1];
                                                                 }
                                                             });
        
        minq.offer(intervals[0]);
        for(int i = 1; i < n; ++i)
        {
            int[] curr = intervals[i];
            int[] earliestFree = minq.poll();
            
            if(curr[0] >= earliestFree[1]) // reuse
            {
                // update how long it will be occupied
                earliestFree[1] = Math.max(earliestFree[1], curr[1]);
            }
            else // needs a separate room
            {
                minq.offer(curr);
            }
            
            minq.offer(earliestFree);
        }
        
        return minq.size();
    }
}


Runtime: 8 ms, faster than 53.61% of Java online submissions for Meeting Rooms II.
Memory Usage: 37.9 MB, less than 74.91% of Java online submissions for Meeting Rooms II.

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: [""]

Idea – 1

If we have n open/close parentheses, we could try each of possibilities and group the valid ones by length. Then the valid group with the longest length would be our solution. Time complexity and space complexity .

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        HashMap<Integer, HashSet<String>> map = new HashMap<>();
        collect(s, 0, "", map);
        
        int max = 0;
        for(int k : map.keySet())
        {
            max = Math.max(max, k);
        }
        
        return new ArrayList<String>(map.get(max));
    }
    
    private void collect(String s, int i, String curr, HashMap<Integer, HashSet<String>> ans)
    {
        if(i >= s.length())
        {
            if(valid(curr))
            {
                HashSet<String> grp = ans.getOrDefault(curr.length(), new HashSet<>());
                grp.add(curr);
                ans.put(curr.length(), grp);
            }
            
            return;
        }
        
        char c = s.charAt(i);
        
        if(Character.isLetter(c))
        {
            collect(s, i+1, curr+c, ans);
        }
        else
        {
            collect(s, i+1, curr, ans);
            collect(s, i+1, curr+c, ans);
        }
    }
    
    private boolean valid(String candidate)
    {
        int n = candidate.length();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i = 0; i < n; ++i)
        {
            char c = candidate.charAt(i);
            if(c == '(')
            {
                stack.addLast(c);
            }
            else if(c == ')')
            {
                if(stack.isEmpty())
                {
                    return false;
                }
                
                char top = stack.removeLast();
                if(top != '(')
                {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}


Runtime: 246 ms, faster than 5.01% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 44.5 MB, less than 17.57% of Java online submissions for Remove Invalid Parentheses.

Idea - 2

Since we need to delete min number of parentheses to make it valid, we can consider the output of deleting a parenthesis as a neighbor of current string and thus a BFS would give us the result, actually all valids in an entire level of BFS. Say the input has n characters in it, then it would produce n neighbors each having length n-1, each of these neighbors would produce n-1 neighbors having length n-2, etc. So the time complexity is and space would be .

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        HashSet<String> set = new HashSet<>();
        HashSet<String> visited = new HashSet<>();
        
        Deque<String> q = new ArrayDeque<>();
        q.addLast(s);
        visited.add(s);
        
        boolean found = false;
        while(!q.isEmpty())
        {
            int n = q.size();
            while(n-- > 0)
            {
                String front = q.removeFirst();
                if(valid(front))
                {
                    set.add(front);
                    found = true;
                }
                
                if(!found)
                {
                    for(int i = 0; i < front.length(); ++i)
                    {
                        if(Character.isLetter(front.charAt(i)))
                        {
                            continue;
                        }
                        
                        String nei = front.substring(0, i) + front.substring(i+1);
                        if(!visited.contains(nei))
                        {
                            visited.add(nei);
                            q.addLast(nei);
                        }
                    }
                }
            }
        }
        
        return new ArrayList<String>(set);
    }
    
    private boolean valid(String candidate)
    {
        int n = candidate.length();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i = 0; i < n; ++i)
        {
            char c = candidate.charAt(i);
            if(c == '(')
            {
                stack.addLast(c);
            }
            else if(c == ')')
            {
                if(stack.isEmpty())
                {
                    return false;
                }
                
                char top = stack.removeLast();
                if(top != '(')
                {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
}


Runtime: 52 ms, faster than 36.58% of Java online submissions for Remove Invalid Parentheses.
Memory Usage: 41.6 MB, less than 36.73% of Java online submissions for Remove Invalid Parentheses.

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input: {"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1} 
Explanation: Node 1's value is 1, both of its next and random pointer points to Node 2. Node 2's value is 2, its next pointer points to null and its random pointer points to itself. 

Note:

1. You must return the copy of the given head as a reference to the cloned list.

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        
    }
}

Idea - 1

If we had a singly linked list, we could keep copying each node as we go along. However the random pointer makes it a little complicated. While making copy of a node we might end up making at most 3 copies: one for the node, one for its next, and the third for its random. Now both next (a previous random pointed to the next) and random (random is pointing to an earlier node) of a node could already have been copied. To retrieve such a copy we keep a map from a node to its copy. The algorithm has time complexity and space complexity .

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        }
        
        Node copyHead = new Node(head.val);
        HashMap<Node, Node> map = new HashMap<>();
        map.put(head, copyHead);
        
        Node p = head;
        Node q = copyHead;
        
        while(p != null)
        {
            // invariant: p has already been copied into q
            // we will fix q's next and random here
            
            if(p.next != null)
            {
                Node qnext = map.getOrDefault(p.next, new Node(p.next.val));
                q.next = qnext;
                map.put(p.next, qnext);
            }
            
            if(p.random != null)
            {
                Node qrandom = map.getOrDefault(p.random, new Node(p.random.val));
                q.random = qrandom;
                map.put(p.random, qrandom);
            }
            
            p = p.next;
            q = q.next;
        }
        
        return copyHead;
    }
}


Runtime: 1 ms, faster than 83.25% of Java online submissions for Copy List with Random Pointer.
Memory Usage: 36.8 MB, less than 99.59% of Java online submissions for Copy List with Random Pointer.

Idea - 2

We are using the map to find out where the copy of a given node is. If instead we keep the copy just beside the original node, we do not need the map. We do it in three passes: (1) Make a list of size 2*n where each original node's next will point to its copy and that copy's next will point to the next original node in the original list. (2) We fix random pointer for each copy which is each because the original and copy are adjacent (3) We break the 2*n list into original and copy lists. Time is and space is . Note, we are not counting the size of the out put in space complexity since a deep copy will always require that.

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null)
        {
            return null;
        }
        
        // create 2*n list
        Node p = head;
        while(p != null)
        {
            Node p2 = new Node(p.val);
            Node pnext = p.next;
            p.next = p2;
            p2.next = pnext;
            
            p = pnext;
        }
        
        // fix random pointer of copy
        p = head;
        while(p != null)
        {
            if(p.random != null)
            {
                p.next.random = p.random.next;
            }
            
            p = p.next.next;
        }
        
        Node dummy = new Node(-1);
        Node t = dummy;
        
        // break into two n-size lists
        p = head;
        while(p != null)
        {
            t.next = p.next;
            p.next = p.next.next;
            t = t.next;
            p = p.next;
        }
        
        return dummy.next;
    }
}


Runtime: 0 ms, faster than 100.00% of Java online submissions for Copy List with Random Pointer.
Memory Usage: 34.8 MB, less than 100.00% of Java online submissions for Copy List with Random Pointer.

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [   1->4->5,   1->3->4,   2->6 ] 
Output: 1->1->2->3->4->4->5->6

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        
    }
}

Problem Clarification

We are allowed to modify the given lists to produce the resultant merged list.

Idea - 1

We know how to merge two sorted lists. So, we apply the same idea k-1 times. Merge first and second lists. Merge the result with the third list and so on. Say each list has n nodes. There are then k-1 merges requiring time . The overall time complexity is and space .

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        if(k==0)
        {
            return null;
        }
        
        ListNode result = lists[0];
        for(int i = 1; i < k; ++i)
        {
            result = merge2(result, lists[i]);
        }
        
        return result;
    }
    
    private ListNode merge2(ListNode l1, ListNode l2)
    {
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(l1 != null && l2 != null)
        {
            if(l1.val < l2.val)
            {
                t.next = l1;
                l1 = l1.next;
            }
            else
            {
                t.next = l2;
                l2 = l2.next;
            }
            
            t = t.next;
        }
        
        if(l1 != null)
        {
            t.next = l1;
        }
        else if(l2 != null)
        {
            t.next = l2;
        }
        
        return dummy.next;
    }
}


Runtime: 169 ms, faster than 12.22% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 51.3 MB, less than 5.05% of Java online submissions for Merge k Sorted Lists.

Idea - 2

Actually the first node in the result list must be the one among the heads of the k lists that has minimal value. Thus if we repeatedly pick the min from the k heads we have the merged list. To efficiently pick the min we use a minheap. Time and space .

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> mq = new PriorityQueue<>(new Comparator<ListNode>()
                                                         {
                                                             public int compare(ListNode a, ListNode b)
                                                             {
                                                                 return a.val - b.val;
                                                             }
                                                         });
        
        for(ListNode head : lists)
        {
            if(head != null)
            {
                mq.offer(head);
            }
        }
        
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(!mq.isEmpty())
        {
            ListNode min = mq.poll();
            t.next = min;
            t = t.next;
            
            if(min.next != null)
            {
                min = min.next;
                mq.offer(min);
            }
        }
        
        return dummy.next;
    }
}


Runtime: 5 ms, faster than 91.84% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 40.6 MB, less than 22.83% of Java online submissions for Merge k Sorted Lists.

Idea - 3

We can merger each pair of the given k lists as a result we have k/2 lists. We keep doing the same until we end up with a single list. Time complexity is . Space complexity is .

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        
        if(k==0)
        {
            return null;
        }
        
        while(k > 1)
        {
            k = mergePairs(lists, k);
        }
        
        return lists[0];
    }
    
    private int mergePairs(ListNode[] lists, int n)
    {
        int i = 0;
        int j = 0;
        while(i < n-1)
        {
            lists[j++] = merge2(lists[i], lists[i+1]);
            i += 2;
        }
        
        if(i < n)
        {
            lists[j++] = lists[i];
        }
        
        return j;
    }
    
    private ListNode merge2(ListNode l1, ListNode l2)
    {
        ListNode dummy = new ListNode(0);
        ListNode t = dummy;
        
        while(l1 != null && l2 != null)
        {
            if(l1.val < l2.val)
            {
                t.next = l1;
                l1 = l1.next;
            }
            else
            {
                t.next = l2;
                l2 = l2.next;
            }
            
            t = t.next;
        }
        
        if(l1 != null)
        {
            t.next = l1;
        }
        else if(l2 != null)
        {
            t.next = l2;
        }
        
        return dummy.next;
    }
}


Runtime: 2 ms, faster than 99.90% of Java online submissions for Merge k Sorted Lists.
Memory Usage: 41.5 MB, less than 12.95% of Java online submissions for Merge k Sorted Lists.

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 2³¹ – 1.

Example 1:

Input: 123 
Output: "One Hundred Twenty Three" 

Example 2:

Input: 12345 
Output: "Twelve Thousand Three Hundred Forty Five"

Example 3:

Input: 1234567 
Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" 

Example 4:

Input: 1234567891 
Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

Idea – 1

We can recursively process each named power of tens starting from the highest one going towards lowest, like process billions, then millions, then thousands, etc. Subhundreds have more variation in names like teens, twenties, thirties, etc. Since the input is an integer, basically this is a algorithm. However devil’s in details! For each named power of tens we have a quotient and a remainder. What if there is no remainder?

class Solution {
    private static final int[] units = {1000000000, 1000000, 1000, 100};
    private static final String[] names = {"Billion", "Million", "Thousand", "Hundred"};
    private static final String[] ones = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
    
    private static final String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
    
    private static final String[] teens = {"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
    
    public String numberToWords(int num) {
        StringBuilder sb = new StringBuilder();
        if(num==0)
        {
            return "Zero";
        }        
        
        n2e(num, sb);
        
        return sb.toString().trim();
    }
    
    private void n2e(int num, StringBuilder sb)
    {
        for(int i = 0; i < units.length; ++i)
        {
            int unit = units[i];
            if(num >= unit)
            {
                n2e(num/unit, sb);
                sb.append(String.format(" %s", names[i]));
                
                num %= unit;
            }
        }
        
        if(num > 0)
        {
            int t = num/10;
            if(t == 0)
            {
                sb.append(String.format(" %s", ones[num]));
            }
            else if(t == 1)
            {
                sb.append(String.format(" %s", teens[num%10]));
            }
            else
            {
                sb.append(String.format(" %s", tens[t]));
                if(num%10 > 0)
                {
                    sb.append(String.format(" %s", ones[num%10]));    
                }
            }    
        }
    }
}


Runtime: 13 ms, faster than 6.23% of Java online submissions for Integer to English Words.
Memory Usage: 38.2 MB, less than 5.18% of Java online submissions for Integer to English Words.

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

Input: [-2,1,-3,4,-1,2,1,-5,4], 
Output: 6 
Explanation: [4,-1,2,1] has the largest sum = 6. 

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

class Solution {
    public int maxSubArray(int[] nums) {
        
    }
}

Problem Clarification

We need to consider sum of contiguous elements.

Idea - 1

Try each of subarray and keep track of the max sum. Time , space .

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int maxsum = Integer.MIN_VALUE;
        
        for(int i = 0; i < n; ++i)
        {
            int sum = 0;
            for(int j = i; j < n; ++j)
            {
                sum += nums[j];
                maxsum = Math.max(maxsum, sum);
            }
        }
        
        return maxsum;
    }
}


Runtime: 105 ms, faster than 5.03% of Java online submissions for Maximum Subarray.
Memory Usage: 49.3 MB, less than 5.05% of Java online submissions for Maximum Subarray.

Idea - 2

While considering if we should include to the running sum, if the sum of does not help then we start a fresh run starting at . The algorithm has time and space .

class Solution {
    public int maxSubArray(int[] nums) {
        int maxsum = Integer.MIN_VALUE;
        int sum = 0;
        for(int i = 0; i < nums.length; ++i)
        {
            sum = Math.max(sum+nums[i], nums[i]);
            maxsum = Math.max(maxsum, sum);
        }
        
        return maxsum;
    }
}


Runtime: 1 ms, faster than 97.15% of Java online submissions for Maximum Subarray.
Memory Usage: 38.4 MB, less than 92.18% of Java online submissions for Maximum Subarray.

Idea - 3

If we break the array in middle and find solutions: one to the left and other to the right, then the global solution would be the maximum among these two solutions and the solution that cross boundary. Time and stack space .

class Solution {
    public int maxSubArray(int[] nums) {
        return maxSum(nums, 0, nums.length-1);
    }
    
    private int maxSum(int[] A, int lo, int hi)
    {
        if(lo > hi)
        {
            return 0;
        }
        
        if(lo == hi)
        {
            return A[lo];
        }
        
        int mid = lo+(hi-lo)/2;
        
        int leftSum = maxSum(A, lo, mid);
        int rightSum = maxSum(A, mid+1, hi);
        
        // last element to the left and first element
        // to the right must be in the crossing solution
        //
        int middleSum = mid+1 > hi ? 0 : A[mid+1];
        middleSum += A[mid];
        
        // can we increase going to the right
        //
        int sum = middleSum;
        for(int j = mid+2; j <= hi; ++j)
        {
            sum += A[j];
            middleSum = Math.max(middleSum, sum);
        }
        
        // can we increase going to the left
        //
        sum = middleSum;
        for(int j = mid-1; j >= lo; --j)
        {
            sum += A[j];
            middleSum = Math.max(middleSum, sum);
        }
        
        return Math.max( middleSum, Math.max(leftSum, rightSum) );
    }
}


Runtime: 3 ms, faster than 74.42% of Java online submissions for Maximum Subarray.
Memory Usage: 38.5 MB, less than 92.00% of Java online submissions for Maximum Subarray.

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()" 
Output: true 

Example 2:

Input: "()[]{}" 
Output: true 

Example 3:

Input: "(]" 
Output: false 

Example 4:

Input: "([)]" 
Output: false 

Example 5:

Input: "{[]}" 
Output: true

class Solution {
    public boolean isValid(String s) {
        
    }
}

Problem Clarification

Idea - 1

A close must always be preceded by an open of the right kind. If we use a stack, and on seeing a close if we pop the right kind of open from the stack, then in the end either there will be only opens left or the stack would be empty - later would be the valid case. The algorithm has time and space .

class Solution {
    
    private static final String closes = ")}]";
    
    public boolean isValid(String s) {
        int n = s.length();
        Deque<Character> stack = new ArrayDeque<>();
        for(int i = 0; i < n; ++i)
        {
            char c = s.charAt(i);
            
            if(closes.indexOf(c) >= 0)
            {
                if(stack.isEmpty() || !match(c, stack.removeLast()))
                {
                    return false;
                }
            }
            else
            {
                stack.addLast(c);
            }
        }
        
        return stack.isEmpty();
    }
    
    private boolean match(char close, char open)
    {
        if(closes.indexOf(open) >= 0)
        {
            return false;
        }
        
        return (close==')' && open=='(')
            || (close=='}' && open=='{')
            || (close==']' && open=='[');
    }
}


Runtime: 1 ms, faster than 99.54% of Java online submissions for Valid Parentheses.
Memory Usage: 35.6 MB, less than 36.87% of Java online submissions for Valid Parentheses.