This AC code is O(n) or O(n^2) ?


  • 0
    N

    I thought it was O(n^2), case the second loop is still need n worst time, could you help change it to O(n)?

    public String minWindow(String S, String T) {
        HashMap<Character, Integer> needFind = new HashMap<Character, Integer>();
        HashMap<Character, Integer> hasFind = new HashMap<Character, Integer>();
        
        if (S == null || S.isEmpty() || T == null || T.isEmpty()) {
            return "";
        }
        
        for (int i = 0; i < T.length(); i++) {
            char key = T.charAt(i);
            if (!needFind.containsKey(key)) {
                needFind.put(key, 1);
            } else {
                needFind.put(key, needFind.get(key) + 1);
            }
        }
        
        int target = T.length();
        int count = 0;
        int start = 0;
        String minStr = null;
        for (int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            if (!needFind.containsKey(c)) {
                continue;
            }
            
            if (!hasFind.containsKey(c)) {
                hasFind.put(c, 1);
                count++;
            } else {
                hasFind.put(c, hasFind.get(c) + 1);
                if (hasFind.get(c) <= needFind.get(c)) {
                    count++;
                }
            }
            
            if (count == target) {
                int j = start;
                for (; j < i; j++) {
                    char cj = S.charAt(j);
                    if (!needFind.containsKey(cj)) {
                        continue;
                    }
                    if (hasFind.get(cj) <= needFind.get(cj)) {
                        break;
                    }
                    hasFind.put(cj, hasFind.get(cj) - 1);
                }
                if (minStr == null || minStr.length() > i - j + 1) {
                    minStr = S.substring(j, i + 1);
                }
                start = j;
            }
        }
        
        return minStr == null ? "" : minStr;
    }
    

    how about use a queue to store the index of hasFind char, like below, is this still O(n^2). n is the length of S.

            // use to store all need char index.
            queue.offer(i);
            if (count == target) {
                Integer j = null;
                while ((j = queue.peek()) != null) {
                    char cj = S.charAt(j);
                    if (!needFind.containsKey(cj)) {
                        continue;
                    }
                    
                    if (hasFind.get(cj) <= needFind.get(cj)) {
                        break;
                    }
                    hasFind.put(cj, hasFind.get(cj) - 1);
                    queue.poll();
                }
                
                if (minStr == null || minStr.length() > i - j + 1) {
                    minStr = S.substring(j, i + 1);
                }
            }

  • 0
    D

    I believe your solution is O(n). Either index i or index j increases in every iteration. Index i goes from 0 ... length S. Index j can go from 0 ... length S. In the worst case, your solution runs in 2 * n, which is still O(n).


  • 0
    N

    pay attention, the index j loop is in index i loop..


  • 0
    D

    I am aware that index j loop is in index i loop. Nested loops do not always mean your algorithm is O(n^k). Think about this way, your inner loop doesn't always start from the beginning; it starts from where you left off.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.