Ice Cream Parlor

  • + 0 comments

    Java solution in O(n) time and O(m) space.

        public static List<Integer> icecreamParlor(int m, List<Integer> arr) {
            List<Integer> result = new ArrayList<>(2);
            int[] contained = new int[m + 1];
            Arrays.fill(contained, -1);
            for (int i = 0; i < arr.size(); i++) {
                Integer num = arr.get(i);
                if (num > m) continue;
                int diff = m - num;
                if (contained[diff] > -1) {
                    result.add(contained[diff] + 1);
                    result.add(i + 1);
                    break;
                }
                if (contained[num] == -1) {
                    contained[num] = i;
                }
            }
            return result;
        }