Add Two Numbers - LeetCode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Java Solution :

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        int sum = carry + x + y;
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
    }
}

Two Sum II - Input array is sorted - LeetCode

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

• Your returned answers (both index1 and index2) are not zero-based.
• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.

Java Solution :

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        for(int i=0; i < numbers.length ; i++){
            if(map.containsKey(target-numbers[i]) && i!=map.get(target-numbers[i])){
                return new int [] {map.get(target-numbers[i])+1,i+1};
            }else{
                map.put(numbers[i],i);
            }
        }
        return null;
    }
}

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: