__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.

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

__Example__**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__

__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].

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

__Note__

__Contiguous Array__Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

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

__Example 1__Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

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

__Example 2__Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

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

__Note__**:**

__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__-K Himaanshu Shuklaa..

## No comments:

## Post a Comment