Find the maximum of non-intersecting segments of length 2 (two adjacent elements), such that segments have an equal sum [closed]

There wasa recent interview where I was asked this question. Given nums = [10, 1, 3, 1, 2, 2, 1, 0, 4], there are three non-overlapping segments, each whose sum is equal to 4: (1, 3), (2, 2), (0, 4). Expected output = 3 Also for test case : [9, 9, 9, 9, 9] the code should return 2. My code below but does not return the correct output, any help would be appreciated? This is my approach so far but need to write in a more efficient way I believe?

 public static int maxNonOverlapping(int[] nums) {
        int[] ends = new int[nums.length + 1];
        Map<Integer, Integer> indexs = new HashMap<>();
        indexs.put(0,0);
        int sum = 0;
        int max = 0;
        for (int i = 0; i < nums.length; i ++) {
            sum += nums[i];
            ends[i + 1] = ends[i];
            if (indexs.containsKey(sum)) {
                ends[i + 1] = Math.max(ends[i + 1], ends[indexs.get(sum)] + 1);
            } 
            indexs.put(sum, i + 1);
        }
        return ends[nums.length];
    }

There was a good suggestion by Harshal below and I am adding the 100% working code here, let me know if anyone thinks of any modification.

public static int maxNonOverlapping(int[] nums) {
    Map<Integer, Integer> indexs = new HashMap<>();
    int prev = 0;
    int count = 0;
    for (int i = 1; i < nums.length; i++) {
        int s = nums[i - 1] + nums[i];
        if (s == prev && count > 0) {
            count--;
            continue;
        }
        prev = s;
        count++;
        indexs.put(s, indexs.getOrDefault(s, 0) + 1);
    }

    return indexs.values().stream().mapToInt(k -> k).max().getAsInt();
}

Answer

public static int maxNonOverlapping(int[] nums) {
    Map<Integer, Integer> indexs = new HashMap<>();
    int max = 0;
    int prev = 0;
    for (int i = 1; i < nums.length; i++) {
        int s = nums[i - 1] + nums[i];
        if (s == prev) {
            continue;
        }
        prev = s;
        indexs.put(s, indexs.getOrDefault(s, 0) + 1);
    }

    return indexs.values().stream().mapToInt(k -> k).max().getAsInt();
}

The idea is to create a Map of sum of the 2 adjacent nums and their count. Keep a previous to avoid overlap. Once you have that, all you need is the maximum key from the Map.

To avoid finding the max key which is another O(n), you can use a TreeMap.

Leave a Reply

Your email address will not be published. Required fields are marked *