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 .

StringBuilder - Java

String Builder :


String Builder is often used if you want use string concatenation very often.


Time complexity will be O(N).

package com.techyield.operationsinarray;

public class StringBuilder {

public static void main(String[] args) {

int n = 10000;

StringBuilder str = new StringBuilder("Hello");

for(int i =0 ; i < n ; i++) {

str.append("satya");

}

String s = str.toString();

}

}

Immutable String - Problem and Solutions

In C++ String is mutable , So there won't be any Problem.

But in Java String is immutable which creates problem and we have to resolve it .

So as String is immutable , If you want to change to change the String you have to create a new String even if you want to change one character .


So if we have to do String Concatenation in Java using '+' . It will take O(N*N) time .

String Concatenation is Slow in Java compared to C++ Which is not noticeable .

In Java Concatenation happens by first allocating enough space for new string and copy the contents from old string and append to the new String.

Time Complexity for a String of length 10 and n = 10000 is :


10+10* 2 +10 * 3 + ...... + 10 * n

= 10 * n * (n+1) / 2

Which will be O(N*N).

Example :

package com.techyield.operationsinarray;

public class StringConcatenation {

public static void main(String[] args) {

String s = "";

int n = 200000;

for(int i =0 ; i< n ;i++) {

s += "hello";

}

}

}

So you want to make String Immutable to Mutable :

Check here : https://techyield.blogspot.com/2019/06/string-immutable-to-mutable-java.html

String Immutable to Mutable (Java) Solutions

If you want your string to covert from Immutable to Mutable then better solution is :

Convert the String to CharArray :

package com.techyield.operationsinarray;

public class StringCharArray {

public static void main(String[] args) {

String s1 ="Sunny G";

char[] array = s1.toCharArray();

array[5] = ',';

System.out.println(array);

}

}