Part 2.3: Leet Code Solutions For Java Coding Interview Round

Counting Elements

Given an integer array arr, count element x such that x + 1 is also in arr. If there're duplicates in arr, count them separately.

Example 1:
Input: arr = [1,2,3]
Output: 2
Explanation: 1 and 2 are counted cause 2 and 3 are in arr.

Example 2:
Input: arr = [1,1,3,3,5,5,7,7]
Output: 0
Explanation: No numbers are counted, cause there's no 2, 4, 6, or 8 in arr.

Example 3:
Input: arr = [1,3,2,3,5,0]
Output: 3
Explanation: 0, 1 and 2 are counted cause 1, 2 and 3 are in arr.

Example 4:
Input: arr = [1,1,2,2]
Output: 2
Explanation: Two 1s are counted cause 2 is in arr.

Constraints:
1 <= arr.length <= 1000
0 <= arr[i] <= 1000

Algorithm:
We will create a hashmap in which the key is the element (from the array), value is the number of occurrence of that element in the array.
Iterate through map, and check if the key with value equal to current key +1 is present in the map or not. If yes, increment the elementCount.

GIT URL: Java Solution of Leet Code's Counting Elements problem

Java Solution

Middle of the Linked List

Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node.

Example 1:
Input: [1,2,3,4,5]
Output: Node 3 from this list (Serialization: [3,4,5])
The returned node has value 3.  (The judge's serialization of this node is [3,4,5]).
Note that we returned a ListNode object ans, such that:
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:
Input: [1,2,3,4,5,6]
Output: Node 4 from this list (Serialization: [4,5,6])
Since the list has two middle nodes with values 3 and 4, we return the second one.

Note:
The number of nodes in the given list will be between 1 and 100.

Algorithm:

• We can traverse the linked list to count the no. of nodes in it. And then traverse it again return the node present at count/2. But in this case we need to traverse twice.
• We can do this in one traversal. For this we need to maintain two pointers.
• First pointer will be the slow one, and the second one will be faster. 
• During each iteration, we will move the slow pointer by one and fast pointer by two.
• When the fast pointer reaches the end, the slow one will be at the middle of the linked list.

GIT URL: Java Solution of Leet Code's Middle of the Linked List problem

Java Solution

Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:
1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

Follow up:
Can you solve it in O(N) time and O(1) space?-K Himaanshu Shuklaa..

Algorithm:

• We will convert both strings in char array.
• While iterating the char array we will check if the character is equal to #.
• If not we will push the characters in Stack, else we will pop from stack.
• After this we will compare both the strings.

GIT URL: Java Solution of Leet Code's Backspace String Compare problem

Java Solution

-K Himaanshu Shuklaa..