Part 2.2: Leet Code Solutions For Java Coding Interview Round

Single Number
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
Algorithm
We can do this problem by XORing all array elements, this will gives us the number with single occurrence. FYI:

• XOR of a number with itself is 0.
• XOR of a number with 0 is number itself

GIT URL: Solution of Leet Code's Single Number problem

Java Solution

Move Zeroes
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

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

Algorithm

• A counter (nonZeroCount) will maintain number of non-zero elements.
• Traverse the array, and check if the element is non-zero. 
• If the element is non-zero, put that element at nums[nonZeroCount] and increment the nonZeroCount.
• After the traversal, all non-zero elements will be shifted to the front-end.
• We need to run a loop again, which will make all element zero from nonZeroCount till the end.

GIT URL: Solution of Leet Code's Move Zeroes problem

Java Solution

Best Time to Buy and Sell Stock II

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.

Algorithm

1. We will start traversing. If the current value is greater than the previous one (difference is greater than 0), then we will consider it as profit and do the transaction (buy and sell).
2. We will keep on adding the profit obtained from every consecutive transaction.
3. The total sum we obtain will be the maximum profit.

GIT URL: Solution of Leet Code's Best Time to Buy and Sell Stock II

Java Solution

Group Anagrams
Given an array of strings, group anagrams together.

Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.
• Algorithm:
• To find if two strings are anagram, we need to sort them and compare. They are anagram if they are equal.
• We will create a map, with key as the sorted string and value is the list of Strings.

GIT URL: Solution of Leet Code's Group Anagrams

Java Solution

-K Himaanshu Shuklaa..