Part 2.4: Leet Code Solutions For Java Coding Interview Round

Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word (last word means the last appearing word if we loop from left to right) in the string.

If the last word does not exist, return 0.

Note: A word is defined as a maximal substring consisting of non-space characters only.

Example: Input: "Hello World", Output: 5

GIT URL: Java Solution of Leet Code's Length of Last Word problem

Java Solution

Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   -- > Returns -3.
minStack.pop();
minStack.top();      -- > Returns 0.

minStack.getMin();   -- > Returns -2.

GIT URL: Java Solution of Leet Code's Min Stack problem

Java Solution

Diameter of Binary Tree
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree
          1
         / \
        2   3
       / \   
      4   5 
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

GIT URL: Java Solution of Leet Code's Diameter of Binary Tree problem

Java Solution

Contiguous Array
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1: Input: [0,1], Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2: Input: [0,1,0], Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Algorithm:
1. Replace all the 0's with -1, this will help us to find out the maximum length subarray with sum = 0.
2. Declare a HashMap, this will help us to find the subarray with sum=0 and start index is not 0.
3. Declare three variables sum, maxLength and endIndex. Initialize maxsize with -1 to handle cases where all 1's or 0's. maxsize=-1 means there is no such subarray.
4. Now we will start iterating, and update the sum.
5. If the sum is equal to 0, increment the maxLength and update endIndex.
6. We will check if the sum is present in the HashMap. If not present add the sum as key and value as index.
7. If the value is present, check if the difference of current index and previously stored value in hash (for the sum) is more than maxsize. If yes, update maxsize and endIndex.
8. Replace all the -1's with 0.

GIT URL: Java Solution of Leet Code's Contiguous Array problem

Java Solution

-K Himaanshu Shuklaa..