Leetcode 1

Question 1

Two Sum

Answer 1

HashTable of Integer, Integer - key:value = nums[i], i
Loop through list and check if complement of current number is in keys. If so, return current index and key value. If not, place new entry

Question 2

Compress String

Answer 2

public int compress(char[] chars) {
        int indexAns = 0, index = 0;
        while(index < chars.length){
            char currentChar = chars[index];
            int count = 0;
            while(index < chars.length && chars[index] == currentChar){
                index++;
                count++;
            }

        chars[indexAns++] = currentChar;
        if(count != 1)
            for(char c : Integer.toString(count).toCharArray()) 
                chars[indexAns++] = c;
    }
    return indexAns;
}

Question 3

Merge Intervals ([1, 3], [2, 6]) -> [1, 6]

Answer 3

Sort all intervals by their start value. Create a new “merged” list and add the first sorted interval into it. Compare it to each subsequent interval and check if the current interval begins after the previous interval ends -> they do not overlap. Otherwise, they do overlap and we update the “end” of the prev interval if it is less than the “end” of the current interval.

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        LinkedList merged = new LinkedList<>();
        for (int[] interval : intervals) {

        if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
            merged.add(interval);
        }

        else {
            merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
        }
    }
    return merged.toArray(new int[merged.size()][]);
} } Time: O(nlogn) to sort, Space: O(logn) to sort in place. Otherwise O(n)

Question 4

Maximum nesting depth of two valid parentheses strings

Answer 4

Consider the most deeply nested subset, which is all we really care about b/c e.g. in “(())()”, the deepest stack is “(())” and the remaining “()” we can put in either A or B. Minimum depth is always ceil(maxDepth/2). Any stack in the sequence that is of max depth less or equal to ceil(globalMaxDepth/2) we can assign any way we want since they cannot increase the max depth of the resulting split. First, get the depth of every index of the string. Second, put all odd-depth parentheses in one group, and all even-depth in the other.

public int[] maxDepthAfterSplit(String seq) {
int n = seq.length();
int[] depthArray = new int[n];

        int depth = 0;
        for (int i = 0; i < seq.length(); i ++) {
            if (seq.charAt(i) == '(' ){
                depth ++;
            }
            depthArray[i] = depth % 2;
            if (seq.charAt(i) == ')') {
                depth --;
            }
        }
        return depthArray;

}Append answer to groups BEFORE d -= 1 because the first ) in "(())" is still depth 2

Question 5

Spiral matrix

Answer 5

base case if matrix is null or empty, return res
res = new ArrayList<>();
int n = matrix.length, m = matrix[0].length;
int up = 0, down = n - 1;
int left = 0, right = m - 1;
while res.size() < n*m
for (int j = left; j <= right && res.size() < n * m; j++)
res.add(matrix[up][j]);
for (int i = up + 1; i <= down - 1 && res.size() < n * m; i++)
res.add(matrix[i][right]);

        for (int j = right; j >= left && res.size() < n * m; j--)
            res.add(matrix[down][j]);

        for (int i = down - 1; i >= up + 1 && res.size() < n * m; i--) 
            res.add(matrix[i][left]);

        left++; right--; up++; down--;

Question 6

Flatten Nested List Iterator

Answer 6

Use a stack of ListIterators. private Stack> lists;

Deque stack = new ArrayDeque<>();
    public NestedIterator(List nestedList) {
        prepareStack(nestedList);
    }

    @Override
    public Integer next() {
        if (!hasNext()) {
            return null;
        }
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        while (!stack.isEmpty() && !stack.peek().isInteger()) {
            List list = stack.pop().getList();
            prepareStack(list);
        }
        return !stack.isEmpty();
    }

private void prepareStack(List nestedList) {
    for (int i = nestedList.size() - 1; i >= 0; i--) {
        stack.push(nestedList.get(i));
    }
}

Question 7

Find duplicate file in system

Answer 7

HashMap < String, List < String&raquo_space; map = new HashMap < > ();
for (String path: paths) {
String[] values = path.split(“ “);
for (int i = 1; i < values.length; i++) {
String[] name_cont = values[i].split(“\(“);
name_cont[1] = name_cont[1].replace(“)”, “”);
List < String > list = map.getOrDefault(name_cont[1], new ArrayList < String > ());
list.add(values[0] + “/” + name_cont[0]);
map.put(name_cont[1], list);
}
}

Loop through finished HashMap and check if each list of values has length > 1, if so then add to output ArrayList

Time: O(n * k), n strings of average length k. space: O(n*k) for hashmap and result

Question 8

Binary Tree Pruning

Answer 8

Use recursion with base case if root is null, return null. Otherwise, root.left = pruneTree(root.left); root.right = pruneTree(root.right); if root.val == 0 && root.left == null && root.right == null, root = null; return root

Time: O(N) where n is the number of nodes in the tree b/c we process each node once. space: O(n) worst case if recursion call stack is height H of the tree (tree could be skewed)

Question 9

Consecutive characters

Answer 9

increase the counter by 1 if current char is same as prev one, otherwise reset the counter to 1 (start with max and index both equal to 1)
Update max value of the counter during each iteration
O(N) time and O(1) space

Question 10

Add two numbers (linked lists)

Follow up: what if digits stored in non-reversed order?

Answer 10

ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
Time: O(max(m, n)) Space: O(max(m, n) + 1)