[C++] [Java] Clean Code - Overflow Map


  • 1

    C++

    class Solution {
    public:
        /**
         * 1. keep track of accumulated 1s at each point.
         * 2. at each point, if there is more 1s than 0s, we call it an one-overflow;
         * 3. if no previous record, record the position where this overflow happend;
         * 4. if there is previous record, cut off sub-array where that overflow first occur will give you the even 2nd part;
         */
        int findMaxLength(vector<int>& nums) {
            int maxsize = 0;
            int ones = 0;
    
            map<int, int> map;
            map[0] = -1;
            for (int i = 0; i < nums.size(); i++) {
                ones += nums[i];
                int overflow = ones - (i + 1 - ones);
                if (map.count(overflow)) {
                    maxsize = max(maxsize, i - map[overflow]);
                }
                else {
                    map[overflow] = i;
                }
            }
    
            return maxsize;
        }
    };
    

    Java

    public class Solution {
        public int findMaxLength(int[] nums) {
            int maxsize = 0;
            int ones = 0;
    
            Map<Integer, Integer> map = new HashMap<Integer, Integer>();
            map.put(0, -1);
            for (int i = 0; i < nums.length; i++) {
                ones += nums[i];
                int overflow = ones - (i + 1 - ones);   // extra 1s than 0s
                if (map.containsKey(overflow)) {
                    maxsize = Math.max(maxsize, i - map.get(overflow));
                }
                else {
                    map.put(overflow, i);
                }
            }
    
            return maxsize;        
        }
    }
    

Log in to reply
 

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