Contains Duplicate - LeetCode

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true

Example 2:

Input: [1,2,3,4]
Output: false

Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

Java Solution 1:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        int k=0;
        for(int i =1;i < nums.length;i++){
            if(nums[i]==nums[k]){
                return true; 
            }
            k++;
        }
        return false;
    }
}

Java Soluton 2:

class Solution {
    public boolean containsDuplicate(int[] nums) {
        if(nums ==null || nums.length == 0)
            return false;
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i : nums){
            if(!set.add(i))
                return true;
        }
        return false;
    }
}

Java Solution 3:

Remove Duplicates from Sorted Array - LeetCode

Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],

Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Solution 1:

class Solution {
    public int removeDuplicates(int[] nums) {
        int k =0;
        for(int i =0;i < nums.length; i++){
            if( nums[k]!=nums[i]){
                nums[k]=nums[i];
                k++;
            }
        }
        return k;
    }
}

Solution : 2

class Solution {
    public int removeDuplicates(int[] nums) {
       Map<Integer,Integer> map = new HashMap<>();
        int k =0;
        for(int i =0;i < nums.length; i++){
            if(!map.containsKey(nums[i])){
                map.put(nums[i],i);
                nums[k]=nums[i];
                k++;
            }
        }
        return k;
    }
}

Two Sum - LeetCode Solution

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Java Solution:

Approach : One Pass HashTable

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i =0; i< nums.length;i++){
            int element = target-nums[i];
            if(map.containsKey(element) && map.get(element)!=i)
                return new int[]{i,map.get(element)};
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No two sum solution");

         }
}

Time Complexity : O(n)

Space Complexity : O(n)

Other Approaches:

https://techyield.blogspot.com/2019/06/two-sum-leetcode-solution.html

https://techyield.blogspot.com/2019/06/two-sum-leetcode-solution.html

Two Sum - LeetCode Solution

Two Sum - LeetCode Solution

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Java Solution:

Approach : Two Pass Hash Table

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i =0 ;i < nums.length;i++){
            map.put(nums[i],i);
        }
        for(int i =0; i< nums.length;i++){
            int element = target-nums[i];
            if(map.containsKey(element) && map.get(element)!=i)
                return new int[]{i,map.get(element)};
        }
        throw new IllegalArgumentException("No two sum solution");

         }
}

Time Complexity : O(n) HashTable reduces lookup time to O(1).

Space Complexity : O(n) This space is used by hashtable to store the number of elements n.

Two Sum - LeetCode Solution

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Java Solution:

Approach : Brute Force

In Brute Force Approch we will iterate through each element x of array and if there is any element equal target-x. Then we will return the index of both elements.

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

Time Complexity : O(n*n)

Space Complexity : O(1)

Remove Element - LeetCode Solution

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example 1:

Given nums = [3,2,2,3], val = 3,

Your function should return length = 2, with the first two elements of nums being 2.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,1,2,2,3,0,4,2], val = 2,

Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.

Note that the order of those five elements can be arbitrary.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeElement(nums, val);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Java Solution :

class Solution {
    public int removeElement(int[] nums, int val) {
        // Here we use Two Pointer Technique 
        int j = 0; // Slow Pointer
        for(int i =0; i < nums.length ;++i){
            if(nums[i] != val){
                nums[j] = nums[i];
                j++;
            }
        }
                return j;
    }
}

Two Pointer Technique In Arrays

In general we will iterate the array using one pointer starting from the first element and ending at the last element.

Sometimes we need two pointers at the same time one pointer from starting element and the other element from the last element.


Example :

Reverse the Array :


Here we will swap the first element with last one until it reaches the middle position.


We use two pointers at the same time to do the iteration :

One starts from the first element and the other pointer starts from the last element .

Swapping takes places until the two pointers meet each other.

package com.techyield.operationsinarray;

public class ReverseArrayUsingTwoPointers {

public static void main(String[] args) {

int a[] = {1,2,3,4,5,6,7,8,9,10};

int i = 0;

int j = a.length-1;

int temp = 0;

while(i<j) {

temp = a[i];

a[i] = a[j];

a[j] = temp;

i++;

j--;

}

for(int b : a)

System.out.print(" "+b);

}

}

Output :

 10 9 8 7 6 5 4 3 2 1

NOTE:

Scenarios where you need to use two-pointer technique:

1. Iterate the array from two ends to middle.

2. One pointer starts from the beginning while the other pointer starts from the end.

So this technique often we use in sorted array .