Java | Prefix Sum and HashMap | With comments and example
\nclass Solution {\n    /*\n        [3, 1, 10, 2], p = 6\n        sum = 3 + 1 + 10 + 2 = 16\n        16 % 6 = 4, we find the shrortest subarray with remainder =
```\nclass Solution {\n    /*\n        [3, 1, 10, 2], p = 6\n        sum = 3 + 1 + 10 + 2 = 16\n        16 % 6 = 4, we find the shrortest subarray with remainder = 4;\n        \n        We use a hashmap with rem at that point as key, and idx as value.\n        Initially len = n = 4\n        \n        At idx -1,  rem = 0;    Map = {0: -1}\n        \n        At idx 0,   rem = 3;    we check if ((3 - 4) % 6 + 6) % 6 = 5 exists as Key? No.    Map = {0: -1, 3: 0}\n        \n        At idx 1,   rem = 4,    we check if ((4 - 4) % 6 + 6) % 6 = 0 exists as Key? Yes.   Map = {0: -1, 3: 0, 4: 1}\n                                len = min(4, idx - map[0]) = min(4, 1 - (-1)) = 2\n                                \n        At idx 2,   rem = 2     we check if ((2 - 4) % 6 + 6) % 6 = 4 exists as Key? Yes.   Map = {0: -1, 3: 0, 4: 1, 2: 2}\n                                len = min(2, idx - map[4]) = min(2, 2 - (1)) = 1\n                                \n        At idx 3,   rem = 4;    we check if ((4 - 4) % 6 + 6) % 6 = 0 exists as Key? Yes.   Map = {0: -1, 3: 0, 4: 3, 2: 2} (also update map)\n                                len = min(1, idx - map[0]) = min(1, 3 - (-1)) = 1\n                                \n        return len = 1\n    */\n    public int minSubarray(int[] nums, int p) {\n        \n        long sum = 0;\n        for(int num : nums) {\n            sum = (sum + num) % p; // For large numbers using p as mod\n        }\n        \n        if(sum % p == 0) {\n            return 0;\n        }\n        \n        int rem = ((int)sum % p + p) % p;      // The remainder to remove\n        Map<Integer, Integer> map = new HashMap<>();\n        int n = nums.length;\n        int len = n;\n        long pSum = 0;\n        \n        map.put(0, -1);\n        for(int i = 0; i < n; i ++) {\n            \n            pSum = (pSum + nums[i]) % p;    // For large numbers using p as mod\n            int currRem = ((int)pSum % p + p) % p;\n            map.put(currRem, i);\n            \n            int remToSearch = ((currRem - rem) % p + p) % p;\n            if(map.containsKey(remToSearch)) {\n                len = Math.min(len, i - map.get(remToSearch));\n            }\n            \n        }\n        \n        if(len == n) {\n            return -1;\n        }\n        return len;\n    }\n}\n```
['Prefix Sum', 'Java']