50 DSA-Questions: Arrays #3, #4

#3. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int element : nums) {
            if (map.containsKey(element)) {
                return true;
            }
            map.put(element, 0);
        }
        return false;
    }
}

#4. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[I]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] leftToRight = new int[nums.length];
        leftToRight[0] = 1;
        leftToRight[1] = nums[0];
        for (int i=2; i<nums.length; i++) {
            leftToRight[i] = leftToRight[i-1] * nums[i-1];
        }
        int[] rightToLeft = new int[nums.length];
        rightToLeft[nums.length-1] = 1;
        rightToLeft[nums.length-2] = nums[nums.length-1];
        for (int i=nums.length-3; i>=0; i--) {
            rightToLeft[i] = rightToLeft[i+1] * nums[i+1];
        }
        int[] result = new int[nums.length];
        for (int i=0; i<nums.length; i++) {
            result[i] = leftToRight[i] * rightToLeft[i];
        }
        
        return result;
        // O(n)
    }
}

// SAU, mai rapid:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        // left to right
        result[0] = 1;
        for (int i=1; i<nums.length; i++) {
            result[i] = result[i-1] * nums[i-1];
        }
        // right to left
        int prevFactor = 1;
        for (int i=nums.length-2; i>=0; i--) {
            int value = prevFactor * nums[i+1];
            result[i] *= value;
            prevFactor = value;
        }
        
        return result;
        // O(n)
    }
}