Part 2.5: Leet Code Solutions For Java Coding Interview Round

Perform String Shifts

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:

direction can be 0 (for left shift) or 1 (for right shift).
amount is the amount by which string s is to be shifted.
A left shift by 1 means remove the first character of s and append it to the end.
Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.
Return the final string after all operations.

Example 1:
Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation:
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

Example 2:
Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation:
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

Constraints:
1 <= s.length <= 100
s only contains lower case English letters.
1 <= shift.length <= 100
shift[i].length == 2
0 <= shift[i][0] <= 1
0 <= shift[i][1] <= 100

GIT URL: Java Solution of Leet Code's Perform String Shifts problem

Java Solution

Last Stone Weight
We have a collection of stones, each stone has a positive integer weight.

Each turn, we choose the two heaviest stones and smash them together.

Suppose the stones have weights x and y with x <= y.  The result of this smash is:

If x == y, both stones are totally destroyed;
If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.
At the end, there is at most 1 stone left.  Return the weight of this stone (or 0 if there are no stones left.)

Example 1:
Input: [2,7,4,1,8,1]
Output: 1

Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.

Note:
1 <= stones.length <= 30

1 <= stones[i] <= 1000

GIT URL: Java Solution of Leet Code's Last Stone Weight problem

Java Solution

Product of Array Except Self
Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:
Input:  [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Algorithm:
1). create a new array 'output' with the length same as the input array 'nums'. In 'output' array for a given index i, output[i] would contain the product of all the numbers to the left of i and product of all the numbers to the right of i.
2). We will first find the product of all the elements to the left. To do this let's assume in 'output' array for a given index i, output[i] would contain the product of all the numbers to the left of i.
3). For the element at index '0', there are no elements to the left, that's why output[0]= 1
4). output[i-1] will have the product of elements to the left of 'i-1', to do this we need to multiply nums[i - 1] with output[i-1]
5). Declare a int variable 'right', which cntains the product of all the elements to the right.
6). For the last element (the element at index 'length-1') there are no elements to the right, that's why R will be 1.

7). We need to update output[i] it will be the product of output[i] and 'right'. After doing this we need to update 'right' (it would be product of 'right' and nums[i]).

GIT URL: Java Solution of Leet Code's Product of Array Except Self problem

Java Solution

-K Himaanshu Shuklaa..