Segment Tree

307. Range Sum Query - Mutable

    SegmentTreeNode root;
    int[] nums;
    public NumArray(int[] nums) {
        this.nums = nums;
        root = buildSegmentTree(nums, 0, nums.length - 1);
    }

    private SegmentTreeNode buildSegmentTree(int[] nums, int s, int e) {
        if (e < s) return null;
        if (s == e) return new SegmentTreeNode(s, e, nums[s]);
        SegmentTreeNode curt = new SegmentTreeNode(s, e);
        curt.left = buildSegmentTree(nums, s, curt.mid);
        curt.right = buildSegmentTree(nums, curt.mid + 1, e);
        curt.sum = curt.left.sum + curt.right.sum;
        return curt;
    }

    public void update(int i, int val) {
        nums[i] = val;
        updateHelper(i, val, root);
    }

    private void updateHelper(int i, int val, SegmentTreeNode curt) {
        if (curt.start == curt.end && curt.start == i) {
            curt.sum = val;
            return;
        }
        if (i > curt.mid) {
            updateHelper(i, val, curt.right);
        } else {
            updateHelper(i, val, curt.left);
        }
        curt.sum = curt.left.sum + curt.right.sum;
    }

    public int sumRange(int i, int j) {
        return sumHelper(i, j, root);
    }

    private int sumHelper(int i, int j, SegmentTreeNode curt) {
        if (curt.start == i && curt.end == j) return curt.sum;
        if (j <= curt.mid) {
            return sumHelper(i, j, curt.left);
        } else if (i > curt.mid) {
            return sumHelper(i, j, curt.right);
        } else {
            return sumHelper(i, curt.mid, curt.left) + sumHelper(curt.mid + 1, j, curt.right);
        }
    }

    class SegmentTreeNode {
        int start, end, mid;
        int sum;
        SegmentTreeNode left, right;

        SegmentTreeNode(int start, int end) {
            this.start = start;
            this.end = end;
            this.mid = start + (end - start) / 2;
        }
        SegmentTreeNode(int start, int end, int sum) {
            this.start = start;
            this.end = end;
            this.mid = start + (end - start) / 2;
            this.sum = sum;
        }
    }

Good Subarray

An array is good if all subarrays have atleast 1 element in them whose frequency is 1.

For Example :

Good : 1,2,1
Good: 1,2,5,2,4,3,4
Bad: 1,2,3,1,2,3

Since all subarrays [1], [1,2], [2,1], [1,2,1] have at least 1 element that occurs once. Expected Time Complexity : O(NlogN)

public boolean goodsubarray(int[] arr, int start, int end) {
    if(start < 0 || end > arr.length || end - start <= 1) return true;
    Map<Integer, Integer> freq = new HashMap<>();
    Map<Integer, Integer> index = new HashMap<>(); 
    for(int i = start; i < end; i++) {
        freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
        index.put(arr[i], i);
    }
    int idx = -1;
    for(int cur: freq.keySet()) {
        if(freq.get(cur) == 1) {
            idx = index.get(cur);
            break;
        }
    }
    if(idx == -1) return false;
    return helper(arr, start, idx) && helper(arr, idx +1, end);
}