Merge K sorted lists

/**
 * 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 {
    class HeapNode {
        ListNode n;
        int id;
        
        public HeapNode(ListNode node, int index) {
            n = node;
            id = index;
        }
    }
    
    class HeapNodeComparator implements Comparator<HeapNode> {
        public int compare (HeapNode h1, HeapNode h2) {
            return Integer.compare(h1.n.val, h2.n.val);
        }
    }
    
    PriorityQueue<HeapNode> minHeap = new PriorityQueue<HeapNode>(new HeapNodeComparator());
    
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0)
            return null;
        
        initHeap(lists);
        
        return buildMergedList(lists);
    }
    
    private ListNode buildMergedList(ListNode[] lists) {
        ListNode h = null;
        ListNode t = null;
        
        while(!minHeap.isEmpty()) {
            HeapNode cur = minHeap.poll();
            
            if (h == null && t == null) {
                h = cur.n;
                t = cur.n;
            } else {
                t.next = cur.n;
                t = t.next;
            }
            
            int index = cur.id;
            
            if (lists[index] != null) {
                ListNode temp = lists[index].next;
                lists[index].next = null;
                HeapNode nextNode = new HeapNode(lists[index], index);
                minHeap.offer(nextNode);
                lists[index] = temp;
            }
        }
        
        return h;
    }
    
    private void initHeap(ListNode[] lists) {
        for (int i = 0; i<lists.length; i++) {
            if (lists[i] != null) {
                ListNode temp = lists[i].next;
                lists[i].next = null;
                HeapNode h = new HeapNode(lists[i], i);
                minHeap.offer(h);
                lists[i] = temp;
            }
        }
    }
}

Valid Number

class Solution {
    /**
    * Check if there is any exponent component -> indexOf ('e' || 'E')
    * If none, then
        * Validate only decimalOrInt
    * Else 
        * Validate decimalOrInt
        * Validate Exponent
    * Validte decimalOrInt
        * Is there a '.'
        * If yes, split and validateDecimal (only numeric and sign char)
        * Else validate Integer (only numeric and sign char)
    * Validate the exponent
        * validate number (only numeric)
    */
    public boolean isNumber(String s) {
        if (s.length() == 0)
            return false;
        
        int exponentIdx = getExponentIndex(s);
        
        if (exponentIdx > 0) {
            String exponent = s.substring(exponentIdx, exponentIdx+1);
            String[] components = s.split(exponent);
            return validateNumberWithExponent(components);
        } else {
            return validateNumber(s);
        }
    }
    
    private boolean validateNumberWithExponent(String[] components) {
        boolean validNumber = (components.length == 2);
        validNumber = validNumber && components[0].length() > 0 && validateNumber(components[0]);
        validNumber = validNumber && components[1].length() > 0 && validateExponent(components[1]);
        return validNumber;
    }
    
    private boolean validateExponent(String s) {
        if (!Character.isDigit(s.charAt(0)) && (s.charAt(0) != '+' && s.charAt(0) != '-'))
            return false;
        
        if (s.charAt(0) == '+' || s.charAt(0) == '-') {
            s = s.substring(1);
            if (s.length() == 0)
                return false;
        }
        return validateInteger(s);
    }
    
    private boolean validateNumber(String s) {
        if (!Character.isDigit(s.charAt(0)) && (s.charAt(0) != '+' && s.charAt(0) != '-' && s.charAt(0) != '.'))
            return false;
        
        if (s.charAt(0) == '+' || s.charAt(0) == '-') {
            s = s.substring(1);
            if (s.length() == 0)
                return false;
        }

        int decimalIdx = getDecimalIndex(s);
        
        if (decimalIdx >=0 ) {
            String[] components = s.split("\\.");
            
            boolean valid = components.length > 0;
            
            for (String component: components) {
                valid = (valid && validateInteger(component));
            }
            return valid;
            
        } else {
            return validateInteger(s);
        }
    }
    
    private boolean validateInteger(String s) {
        if (s.length() == 0)
            return true;
        int i = 0;
        while(i < s.length()) {
            char c = s.charAt(i);
            if (!Character.isDigit(c))
                return false;
            i++;
        }
        return true;
    }
    
    private int getDecimalIndex(String s) {
        int decimalCount = cCount(s, '.');

        if (decimalCount > 1)
            return -1;
        
        return s.indexOf('.');
    }
    
    private int getExponentIndex(String s) {
        int expCount = cCount(s, 'e');
        
        if (expCount > 1)
            return -1;
        
        expCount = cCount(s, 'E');
        if (expCount > 1)
            return -1;
        
        int lower = s.indexOf('e');
        int upper = s.indexOf('E');
        
        return lower >=0 ? lower : upper;
    }
    
    private int cCount(String s, char c) {
        int count  = 0;
        int i = 0;
        
        while(i < s.length()) {
            char ch = s.charAt(i);
            //System.out.println(c + " "+ch);
            if (ch == c)
                count++;
            i++;
        }
        return count;
    }
}

2 sum with duplicates

class PairSums {

  // Add any helper functions you may need here
  

  int numberOfWays(int[] arr, int k) {
    // Write your code here
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
    for (int i = 0; i<arr.length; i++) {
      if (!map.containsKey(arr[i])) {
         map.put(arr[i] , 1);
      } else {
        map.put(arr[i], map.get(arr[i]) + 1);
      }
    }
    
    int count = 0;
    
    /*
    * Here each pair will be counted twice
    * E. G. (a, b) will be counted for key a and key b
    * So need to return half of the count
    */
    for (int i = 0; i<arr.length; i++) {
      int diff = k - arr[i];
      if(map.containsKey(diff)) {
        count+= map.get(diff);
      }
      
      if (diff == arr[i])
        count--;
    }
    
    return count/2;
  }

Minimum Remove to Make Valid Parentheses

class Solution {
    /**
    * A valid pair is considered, when I have seen a left paren first and then I saw a right paren. 
    * 1) find the total count (n) of properly paired parenthesis, so there are n number of '(' and n number of ')'
    * 2) iterate over the string, if you see an '(', add it and decrement counter
            * If you see an ')', add it as well and decrement the counter
            * once the counter reaches 0, do not add any of the respective
    **/
    public String minRemoveToMakeValid(String s) {
        if (s == null || s.length() == 0)
            return s;
        
        int pairCount = getValidParenPairCount(s) ;
        
        return getStringWithValidParen(s, pairCount);
    }
    
    private String getStringWithValidParen(String s, int pairCount) {
        int leftCount = pairCount;
        int rightCount = pairCount;
        
        StringBuilder sb = new StringBuilder();
        int i = 0;
        
        while(i < s.length()) {
            char c = s.charAt(i);
            
            switch(c) {
                case '(':
                    if (leftCount > 0) {
                        sb.append(c);
                        leftCount--;
                    }
                    break;
                case ')':
                    // I have to use a left paren first and then I can take a right paren
                    if (rightCount > 0 && rightCount > leftCount) {
                        sb.append(c);
                        rightCount--;
                    }
                    break;
                default:
                    sb.append(c);
                    break;
            }
            i++;
        }
        return sb.toString();
    }
    
    private int getValidParenPairCount(String s) {
        Stack<Character> st = new Stack<Character>();
        
        int count = 0;
        int i = 0;
        
        while(i < s.length()) {
            char c = s.charAt(i);
            
            switch(c) {
                case '(':
                    st.push(c);
                    break;
                case ')':
                    if (!st.isEmpty()) {
                        st.pop();
                        count++;
                    }
                    break;
                default:
                    break;
            }
            i++;
        }
        return count;
    }
}

One Edit Distance

class Solution {
    /**
    * Exactly one edit distance apart means they cannot be 0 or more than 1 edit distance apart
    * the length diff cannot be more than 1 for insert / delete cases, the length can be same
    * 
    */
    public boolean isOneEditDistance(String s, String t) {
        int m = s.length();
        int n = t.length();
        
        if (m == 0 && n == 0)
            return false;
        
        if (s.equals(t))
            return false;
        
        if (m != n && Math.abs(m-n) > 1)
            return false;
        
        int i = 0;
        int j = 0;
        boolean edited = false;
        
        while (i < m && j < n) {
            char c1 = s.charAt(i);
            char c2 = t.charAt(j);
            
            if (c1 != c2) {
                if (edited)
                    return false;
                edited = true;
                if (m < n)
                    j++;
                else if (n < m)
                    i++;
                else {
                    i++;
                    j++;
                }
            } else {
                i++;
                j++;
            }
        }
        
        return true;
    }
}

Read N Characters Given Read4

// I

/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char[] buf4);
 */
/**
* Ask definition of read4, what are the parameters and what does it return
*/
public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    public int read(char[] buf, int n) {
        if (n == 0)
            return 0;
        
        int readCount = 0;
        boolean eof = false;
        int idx = 0;
        
        while(n > 0 && !eof) {
            char[] buf4 = new char[4];
            
            int numRead = read4(buf4);
            
            eof = numRead < 4;
            
            int writeLimit = Math.min(numRead, n);
            
            for (int i = 0; i<writeLimit; i++) {
                buf[idx++] = buf4[i];
            }
            
            n -= writeLimit;
        }
        return idx;
    }
}

// II

/**
 * The read4 API is defined in the parent class Reader4.
 *     int read4(char[] buf4); 
 */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Number of characters to read
     * @return    The number of actual characters read
     */
    private char[] buf4 = new char[4];
    private int buf4Id = 0;
    private int bufId = 0;
    private int lastBuf4Count = 0;
    
    public int read(char[] buf, int n) {
        if (n <= 0)
            return n;
        bufId = 0;
        int buf4ReadCount = 0;
        
        if (buf4Id > 0) {
            buf4ReadCount = readFromBuf4(buf, n);
        }
        
        n -= buf4ReadCount;
        
        int fileReadCount = 0;
        
        if (n > 0) {
            fileReadCount = readFromFile(buf, n);
        }
        
        return buf4ReadCount + fileReadCount;
    }
    
    private int readFromBuf4(char[] buf, int n) {
        int charAtBuf4 = lastBuf4Count - buf4Id;
        int writeLimit = Math.min(charAtBuf4, n);
        
        for (int i = 1; i<=writeLimit; i++) {
            buf[bufId++] = buf4[buf4Id++];
        }
        return writeLimit;
    }
    
    private int readFromFile(char[] buf, int n) {
        
        boolean eof = false;
        int count = 0;
        
        while(n > 0 && !eof) {
            int readCount = read4(buf4);
            lastBuf4Count = readCount;
            buf4Id = 0;
            
            eof = readCount < 4;
            int writeLimit = Math.min(readCount, n);
            
            for (int i = 1; i<=writeLimit; i++) {
                buf[bufId++] = buf4[buf4Id++];
                count++;
            }
            
            n -= writeLimit;
        }
        return count;
    }
}

Expression Add Operators

class Solution {
    /** for multiplication
    cur-prev+prev*tmp, prev*tmp
    2+3-4* 9, here I need to multiply by 4 which was the exact previous number
    * now the 4 was alreaded insided the current evaluated expression in cur. So I need to deduct it from current to be able to multiply with 
    * the latest number
    
    * The idea here is we iterate over the string, at every iteration, we add one digit to my latest number and try ot add '+', '-' '*'
    *  and evalute, this can be done with DFS. At every step, we create the number from my start index, and then evaluate with previous evaluation result
    */
    public List<String> addOperators(String num, int target) {
        if (num == null)
            return null;
        
        if (num.length() == 0)
            return new ArrayList<String>();
        
        List<String> result = new ArrayList<String>();
        evaluateWithDFS(num, result, "", 0, 0, 0, target);
        return result;
    }
    
    private void evaluateWithDFS(String num, List<String> result, String exprPath, int startIdx, long prevEvalResult, long prevNumber, int target) {
        if (startIdx == num.length()) {
            if (prevEvalResult == target)
                result.add(exprPath);
            return;
        } else {
            for (int i = startIdx; i<num.length(); i++) {
                if (i != startIdx && num.charAt(startIdx)=='0') break;
                String curNumStr = num.substring(startIdx, i+1);
                long curNum = Long.parseLong(curNumStr);
                
                if (startIdx == 0) {
                    evaluateWithDFS(num, result, curNumStr, i+1, curNum, curNum, target);
                } else {
                    // Try '+' operator
                    String[] buildNewExprPath = {exprPath, "+", curNumStr};
                    evaluateWithDFS(num, result, BuildString(buildNewExprPath), i+1, prevEvalResult + curNum, curNum, target);
                    
                    // Try '-' operator
                    String[] buildNewExprPath2 = {exprPath, "-", curNumStr};
                    evaluateWithDFS(num, result, BuildString(buildNewExprPath2), i+1, prevEvalResult - curNum, -curNum, target);
                    
                    // Try '*' operator
                    String[] buildNewExprPath3 = {exprPath, "*", curNumStr};
                    evaluateWithDFS(num, result, BuildString(buildNewExprPath3), i+1, prevEvalResult - prevNumber + prevNumber * curNum, prevNumber * curNum, target);
                }
            }
        }
    }
    
    private String BuildString(String[] str) {
        StringBuilder sb = new StringBuilder();
        
        for (String s : str) {
            sb.append(s);
        }
        
        return sb.toString();
    }
}

Find All Anagrams in a String

class Solution {
    /**
    IDEA: If I know, the count for each character in p
    Then, if in s, I can find a wondow where the character count and unique characters are the same, then
    this window is the anagram for p
    STEP 1: compute the character count map for p
    STEP 2: slide over s and compute character count map, where sMap should have the same length for pCount
    **/
    public List<Integer> findAnagrams(String s, String p) {
        int ns = s.length();
        int np = p.length();
        
        if (ns < np)
            return new ArrayList<Integer>();
        
        Map<Character, Integer> pCount = new HashMap<Character, Integer>();
        Map<Character, Integer> sCount = new HashMap<Character, Integer>();
        
        for (int i = 0; i<np; i++) {
            char c = p.charAt(i);
            
            if (!pCount.containsKey(c)) {
                pCount.put(c, 1);
            } else {
                pCount.put(c, pCount.get(c) + 1);
            }
        }
        
        List<Integer> result = new ArrayList<Integer>();
        
        for (int i = 0; i<ns; i++) {
            char c = s.charAt(i);
            
            if (!sCount.containsKey(c)) {
                sCount.put(c, 1);
            } else {
                sCount.put(c, sCount.get(c) + 1);
            }
            
            if (i >= np) {
                char temp = s.charAt(i-np);
                sCount.put(temp, sCount.get(temp)-1);
                
                if (sCount.get(temp) == 0)
                    sCount.remove(temp);
            }
            
            if (pCount.equals(sCount)) {
                result.add(i-np+1);
            }
        }
        return result;
        
    }
}

Add and Search Word – Data structure design

// EASY version

class WordDictionary {
    Map<Integer, Set<String>> dict;
    
    /** Initialize your data structure here. */
    public WordDictionary() {
        dict = new HashMap<Integer, Set<String>>();
    }
    
    public void addWord(String word) {
        int len = word.length();
        
        if (dict.containsKey(len)) {
            Set<String> words = dict.get(len);
            words.add(word);
            dict.put(len, words);
        } else {
            Set<String> words = new HashSet<String>();
            words.add(word);
            dict.put(len, words);
        }
    }
    
    public boolean search(String word) {
        if (dict.size() == 0)
            return false;
        
        // Try exact match
        if (exactMatchFound(word)) {
            return true;
        }
        
        // Try regEx match
        if (regExMatchFound(word)) {
            return true;
        }
        return false;
    }
    
    private boolean exactMatchFound(String word) {
        int len = word.length();
        if (dict.containsKey(len) && dict.get(len).contains(word)) {
            return true;
        }
        return false;
    }
    
    private boolean regExMatchFound(String word) {
        int len = word.length();
        Set<String> words;
        
        if (!dict.containsKey(len)) {
            return false;
        } else {
            words = dict.get(len);
        }
        
        for (String str: words) {
            if (match(str, word))
                return true;
        }
        return false;
    }
    
    private boolean match(String s1, String s2) {
        if (s2.length() == 0) 
            return s1.length() == 0;
        
        if ((s1.charAt(0) == s2.charAt(0)) || s2.charAt(0) == '.') {
            return match(s1.substring(1), s2.substring(1));
        }
        
        return false;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */


// Efficient with Trie, any string search works better if you can build the dict with trie

class WordDictionary {
    class TrieNode {
        Map<Character, TrieNode> children = new HashMap<Character, TrieNode>();
        boolean word = false;
        
        public TrieNode() {}
    }
    
    TrieNode root;
    
    /** Initialize your data structure here. */
    public WordDictionary() {
        root = new TrieNode();
    }
    
    public void addWord(String word) {
        if (word == null || word.length() == 0)
            return;
        
        TrieNode t = root;
        
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            
            if (!t.children.containsKey(c)) {
                t.children.put(c, new TrieNode());
            }
            
            t = t.children.get(c);
        }
        t.word = true;
    }
    
    public boolean search(String word) {
        return searchInTrie(word, root);
    }

/**
    Worst case string = ".........Z"
    There are 26 keys at each level
    M is the length of the word to be searched
    The (26^M)
    */    

    private boolean searchInTrie(String word, TrieNode t) {
        for (int i = 0; i<word.length(); i++) {
            char c = word.charAt(i);
            if (!t.children.containsKey(c)) {
                if (c == '.') {
                    for (char cNext: t.children.keySet()) {
                        if (searchInTrie(word.substring(i+1), t.children.get(cNext)))
                            return true;
                    }
                }
                return false;
            } else {
                t = t.children.get(c);
            }
        }
        return t.word;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

Range Sum Query 2D – Immutable

// Brute Force
class NumMatrix {
    int[][] numMatric;
    
    public NumMatrix(int[][] matrix) {
        this.numMatric = matrix;
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        
        for (int i = row1; i<=row2; i++) {
            for (int j = col1; j<=col2; j++) {
                sum+= numMatric[i][j];
            }
        }
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

// Faster with row cumulative sum

/*
* Why do we need to do better?
    * if the sumRegion is going to be called many times, doing all those addition will be time comsuming
    * If there is a way to cache the sums and use that for simpler oprations
* Use the idea of cumsum
* For each row in each col of that row, I store the cumSum for that row
* Now the sum for all the rows in row1 - row2, will be a sum of cumSum[col2] - cumSum[col1]
*/
class NumMatrix {
    int[][] rowCumSum;
    
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
        int m = matrix.length;
        int n = matrix[0].length;
        
        rowCumSum = new int[m][n];
        
        for (int r = 0; r<m; r ++) {
            rowCumSum[r][0] = matrix[r][0];
            //System.out.println(r + " "+ rowCumSum[r][0] + " " + matrix[r][0]);
        }
        
        for (int r = 0; r<m; r++) {
            for (int c = 1; c<n; c++) {
                //System.out.println(r + " "+ c + " " + matrix[r][c]);
                rowCumSum[r][c] = matrix[r][c] + rowCumSum[r][c-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        
        for (int i = row1; i<=row2; i++) {
            if (col1 > 0) {
                sum+= (rowCumSum[i][col2] - rowCumSum[i][col1-1]);
            } else {
                sum+= rowCumSum[i][col2];
            }
        }
        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

// CumSum
class NumMatrix {
    int[][] cumSum;
    
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return;
       
        int m = matrix.length;
        int n = matrix[0].length;
        
        cumSum = new int[m+1][n+1];
        
        for (int r = 1; r<=m; r++) {
            for (int c = 1; c<=n; c++) {
                cumSum[r][c] = cumSum[r-1][c] + cumSum[r][c-1] + matrix[r-1][c-1] - cumSum[r-1][c-1];       
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) { 
        return cumSum[row2+1][col2+1] - cumSum[row2+1][col1] - cumSum[row1][col2+1] + cumSum[row1][col1];
    }
}