AlgoPrep's 151 Problems Sheet
link --> Click here
Array
Question 1 :- 189. Rotate Array
Level - - > MediumLink ==>> Click Here
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.
Hint
You are given an integer array arr.
We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.
Return the largest number of chunks we can make to sort the array.
Example 1:
Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
Example 2:
Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
Constraints:
1 <= arr.length <= 2000
0 <= arr[i] <= 108
Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length; // If k's value is grater than the array's length that's why we use this line
rotateArr(nums,0,nums.length-1); // {7,6,5,4,3,2,1}
rotateArr(nums,0,k-1); // {5,6,7,4,3,2,1}
rotateArr(nums,k,nums.length-1); // {5,6,7,1,2,3,4}
}
static void rotateArr(int[] nums,int start,int end){
while(start <= end){
int temp = nums[start];
nums[start] = nums[end];
nums[end]=temp;
start++;
end--;
}
}
}
Question 2: 977. Squares of a Sorted
Link ==>> Click Here
Easy
Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.Example 1:
Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Explanation: After squaring, the array becomes [16,1,0,9,100].
After sorting, it becomes [0,1,9,16,100].
Example 2:
Input: nums = [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums is sorted in non-decreasing order.
Known Solution: -
class Solution {
public int[] sortedSquares(int[] nums) {
int n=nums.length;
for (int i =0;i<n;i++){
nums[i]=nums[i]*nums[i];
}
Arrays.sort(nums);
return nums;
}
}
Question 3: 53. Maximum Subarray(Kadane's Algo)
Medium
Given an integer array nums, find the
subarray
with the largest sum, and return its sum.
Example 1:
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: The subarray [4,-1,2,1] has the largest sum 6.
Example 2:
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
class Solution {
public int maxSubArray(int[] nums) {
int sum = nums[0];
int newSum = nums[0];
for(int i=1;i<nums.length;i++){
sum = Math.max(nums[i],sum+nums[i]);
if(sum > newSum){
newSum = sum;
}
}
return newSum;
}
}
Question 4: 152. Maximum Product Subarray
Attempted ==>> Click Here To Attempt Again
Medium
Given an integer array nums, find a
subarray
that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
====== Pending Solution Attempted ==>> Click Here To Attempt Again========
Question 5: 169. Majority Element Solved
Easy
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2
Constraints:
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
Follow-up: Could you solve the problem in linear time and in O(1) space?
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
int start = nums[0];
int n = nums.length;
return nums[n/2];
}
}
Question 6: 229. Majority Element II
Attempted ==>> Click Here To Attempt Again
Medium
Topics
Companies
Hint
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?
====== Pending Solution Attempted ==>> Click Here To Attempt Again========
Question 7: 556. Next Greater Element III
Medium
Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.
Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.
Example 1:
Input: n = 12
Output: 21
Example 2:
Input: n = 21
Output: -1
Constraints:
1 <= n <= 231 - 1
class Solution {
public int nextGreaterElement(int n) {
char arr[] = (Integer.toString(n)).toCharArray();
int i = arr.length-2;
while(i>=0 && arr[i] >= arr[i+1])
i--;
if(i == -1){
return -1;
}
int k = arr.length-1;
while(arr[k] <= arr[i]){
k--;
}
swap(arr,i,k);
Arrays.sort(arr,i+1,arr.length);
long ans = Long.valueOf(new String(arr));
return (ans > Integer.MAX_VALUE) ? -1: (int)ans;
}
void swap(char[] arr,int i,int j){
char temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
I have not better understanding about this code.
Question 8: 769. Max Chunks To Make Sorted
Medium
link : Click Here
Hint
You are given an integer array arr of length n that represents a permutation of the integers in the range [0, n - 1].
We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.
Return the largest number of chunks we can make to sort the array.
Example 1:
Input: arr = [4,3,2,1,0]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [4, 3], [2, 1, 0] will result in [3, 4, 0, 1, 2], which isn't sorted.
Example 2:
Input: arr = [1,0,2,3,4]
Output: 4
Explanation:
We can split into two chunks, such as [1, 0], [2, 3, 4].
However, splitting into [1, 0], [2], [3], [4] is the highest number of chunks possible.
Constraints:
n == arr.length
1 <= n <= 10
0 <= arr[i] < n
All the elements of arr are unique.
class Solution {
public int maxChunksToSorted(int[] arr) {
int ans = 0;
int n=arr.length;
int currMax = arr[0];
for(int i=0;i<n;i++){
currMax = Math.max(arr[i],currMax);
if(currMax == i){
ans++;
}
}
return ans;
}
}
Question 9 : 768. Max Chunks To Make Sorted II
HardHint
You are given an integer array arr.
We split arr into some number of chunks (i.e., partitions), and individually sort each chunk. After concatenating them, the result should equal the sorted array.
Return the largest number of chunks we can make to sort the array.
Example 1:
Input: arr = [5,4,3,2,1]
Output: 1
Explanation:
Splitting into two or more chunks will not return the required result.
For example, splitting into [5, 4], [3, 2, 1] will result in [4, 5, 1, 2, 3], which isn't sorted.
Example 2:
Input: arr = [2,1,3,4,4]
Output: 4
Explanation:
We can split into two chunks, such as [2, 1], [3, 4, 4].
However, splitting into [2, 1], [3], [4], [4] is the highest number of chunks possible.
Constraints:
1 <= arr.length <= 2000
0 <= arr[i] <= 108
class Solution {
public int maxChunksToSorted(int[] arr) {
int ans = 1;
int n = arr.length;
int leftMax[] = new int[n];
leftMax[0] = arr[0];
int rightMin[] = new int[n];
rightMin[n-1] = arr[n-1];
for(int i=1;i<n;i++){
leftMax[i] = Math.max(arr[i],leftMax[i-1]);
}
for(int i=n-2;i>=0;i--){
rightMin[i] = Math.min(arr[i],rightMin[i+1]);
}
for(int i=0;i<n-1;i++){
if(leftMax[i] <= rightMin[i+1]){
ans++;
}
}
return ans;
}
}
========================================
Last:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Comments
Post a Comment