Best Time to Buy and Sell Stock || -LeetCode

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Java Solution:

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit =0;
        for(int i=1 ; i < prices.length; i++){
            if(prices[i]>prices[i-1])
                maxProfit+=prices[i]-prices[i-1];
        }
        return maxProfit;
    }
}

Move Zeros - LeetCode

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Java Solution :

class Solution {
    public void moveZeroes(int[] nums) {
        int j =0;
        for(int i =0; i < nums.length ; i++){
             if(nums[i] !=0){
                 nums[j] = nums[i];
                 j++;
             }
            }
        while(j < nums.length){
            nums[j++]=0;
        }
        
        }
    }

Intersection of Two Arrays II-LeetCode

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

• Each element in the result should appear as many times as it shows in both arrays.
• The result can be in any order.

Follow up:

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1's size is small compared to nums2's size? Which algorithm is better?
• What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Java Solution :

class Solution {
 public int[] intersect(int[] nums1, int[] nums2) {
  HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();

  for(int i : nums1){
   if(!map.containsKey(i)){
    map.put(i,1); 
   }else{
    map.put(i,map.get(i)+1);
   }
  }
  ArrayList<Integer> list = new ArrayList<Integer>();

  for(int j : nums2){
   if(map.containsKey(j)){
    if(map.get(j)>=1){
     list.add(j);
     map.put(j,(map.get(j))-1);

    }
   }
  }

  int[] common = new int[list.size()];
  int j =0;

  for(int k:list){
   common[j]=k;
   j++;

  }
  return common;
 }
}

Single Number - LeetCode

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

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

Example 2:

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

Java Solution: Using HashSet

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i : nums)
        {
            if(!set.add(i))
                set.remove(i);
        }
        Iterator<Integer> it = set.iterator();
        return it.next();
        
    }
}

Java Solution : Using XOR Operation

class Solution {
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        int x =0;
        for(int n : nums){
            x = x ^ n;
        }
        return x;
    }
}

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