Array Easy Question
Question 1
Largest Element
Given an array ‘arr’ of size ‘n’ find the largest element in the array.
Example:
Input: ‘n’ = 5, ‘arr’ = [1, 2, 3, 4, 5]
Output: 5
Explanation: From the array {1, 2, 3, 4, 5}, the largest element is 5.
Sample input 1:
6
4 7 8 6 7 6
Sample output 1:
8
Explanation of sample input 1:
The answer is 8.
From {4 7 8 6 7 6}, 8 is the largest element.
Sample input 2:
8
5 9 3 4 8 4 3 10
Sample output 2:
10
Expected Time Complexity:
O(n), Where ‘n’ is the size of an input array ‘arr’.
Constraints :
1 <= ‘n’ <= 10^5
1 <= ‘arr[i]’ <= 10^9
Time Limit: 1 sec
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class FindLargestElement {
public static void main(String args[]) {
int arr1[] = {2,5,1,3,0};
System.out.println("The Largest element in the array is: " + sort(arr1));
int arr2[] = {8,10,5,7,9};
System.out.println("The Largest element in the array is: " + sort(arr2));
}
// Brute force Approach
static int sort(int arr[]) {
Arrays.sort(arr);
return arr[arr.length - 1];
}
// optimal Approach using max variable
static int findLargestElement(int arr[]) {
int max= arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max= arr[i];
}
}
return max;
}
}
Question 2
Second Largest Element
You have been given an array ‘a’ of ‘n’ unique non-negative integers.
Find the second largest and second smallest element from the array.
Return the two elements (second largest and second smallest) as another array of size 2.
Example :
Input: ‘n’ = 5, ‘a’ = [1, 2, 3, 4, 5]
Output: [4, 2]
The second largest element after 5 is 4, and the second smallest element after 1 is 2.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1 :
4
3 4 5 2
Sample Output 1 :
4 3
Explanation For Sample Input 1 :
The second largest element after 5 is 4 only, and the second smallest element after 2 is 3.
Sample Input 2 :
5
4 5 3 6 7
Sample Output 2 :
6 4
Expected Time Complexity:
O(n), Where ‘n’ is the size of an input array ‘a’.
Constraints:
2 ≤ ‘n’ ≤ 10^5
0 ≤ ‘a’[i] ≤ 10^9
Time limit: 1 sec
Solution:-
Brute Force Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.io.*;
import java.util.Arrays;
class Test {
static private void getElements(int[] arr, int n) {
if (n == 0 || n == 1) {
System.out.print(-1);
System.out.print(" ");
System.out.print(-1);
System.out.print("\n");
}
Arrays.sort(arr);
int small = arr[1];
int large = arr[n - 2];
System.out.println("Second smallest is " + small);
System.out.println("Second largest is " + large);
}
public static void main(String[] args) {
int[] arr = {
1,
2,
4,
6,
7,
5
};
int n = arr.length;
getElements(arr, n);
}
}
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.io.*;
import java.util.Arrays;
class Test {
static private void getElements(int[] arr, int n) {
if (n == 0 || n == 1) {
System.out.print(-1);
System.out.print(" ");
System.out.print(-1);
System.out.print("\n");
}
int small = Integer.MAX_VALUE;
int second_small = Integer.MAX_VALUE;
int large = Integer.MIN_VALUE;
int second_large = Integer.MIN_VALUE;
int i;
for (i = 0; i < n; i++) {
small = Math.min(small, arr[i]);
large = Math.max(large, arr[i]);
}
for (i = 0; i < n; i++) {
if (arr[i] < second_small && arr[i] != small) {
second_small = arr[i];
}
if (arr[i] > second_large && arr[i] != large) {
second_large = arr[i];
}
}
System.out.println("Second smallest is " + second_small);
System.out.println("Second largest is " + second_large);
}
public static void main(String[] args) {
int[] arr = {
1,
2,
4,
6,
7,
5
};
int n = arr.length;
getElements(arr, n);
}
}
Question 3
Check Sorted Array
You have been given an array ‘a’ of ‘n’ non-negative integers.You have to check whether the given array is sorted in the non-decreasing order or not.
Your task is to return 1 if the given array is sorted. Else, return 0.
Example :
Input: ‘n’ = 5, ‘a’ = [1, 2, 3, 4, 5]
Output: 1
The given array is sorted in non-decreasing order; hence the answer will be 1.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1 :
4
0 0 0 1
Sample Output 1 :
1
Explanation For Sample Input 1 :
The given array is sorted in non-decreasing order; hence the answer will be 1.
Sample Input 2 :
5
4 5 4 4 4
Sample Output 2 :
0
Expected Time Complexity:
O(n), Where ‘n’ is the size of an input array ‘a’.
Constraints:
1 ≤ ‘n’ ≤ 5*10^6
0 ≤ ‘a’[i] ≤ 10^9
Time limit: 1 sec
Solution:-
Brute Force Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Test {
static boolean isSorted(int arr[], int n) {
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[i])
return false;
}
}
return true;
}
public static void main(String args[]) {
int arr[] = {
1,
2,
3,
4,
5
}, n = 5;
System.out.println(isSorted(arr, n));
}
}
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Test {
static boolean isSorted(int arr[], int n) {
for (int i = 1; i < n; i++) {
if (arr[i] < arr[i - 1])
return false;
}
return true;
}
public static void main(String args[]) {
int arr[] = {
1,
2,
3,
4,
5
}, n = 5;
System.out.println(isSorted(arr, n));
}
}
Question 4
Remove Duplicates from Sorted Array
You are given a sorted integer array ‘arr’ of size ‘n’.
You need to remove the duplicates from the array such that each element appears only once.
Return the length of this new array.
Note:
Do not allocate extra space for another array. You need to do this by modifying the given input array in place with O(1) extra memory.
For example:
‘n’ = 5, ‘arr’ = [1 2 2 2 3].
The new array will be [1 2 3].
So our answer is 3.
Detailed explanation ( Input/output format, Notes, Images )
Sample input 1:
10
1 2 2 3 3 3 4 4 5 5
Sample output 1:
5
Explanation of sample input 1:
The new array will be [1 2 3 4 5].
So our answer is 5.
Sample input 2:
9
1 1 2 3 3 4 5 5 5
Sample output 2:
5
Expected time complexity:
The expected time complexity is O(n).
Constraints :
1 <= ‘n’ <= 10^6
-10^9 <= ‘arr[i]’ <=10^9
Where ‘arr[i]’ is the value of elements of the array.
Time limit: 1 sec
`
Brute Force Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;
public class Main {
public static void main(String[] args) {
int arr[] = {1,1,2,2,2,3,3};
int k = removeDuplicates(arr);
System.out.println("The array after removing duplicate elements is ");
for (int i = 0; i < k; i++) {
System.out.print(arr[i] + " ");
}
}
static int removeDuplicates(int[] arr) {
HashSet < Integer > set = new HashSet < > ();
for (int i = 0; i < arr.length; i++) {
set.add(arr[i]);
}
int k = set.size();
int j = 0;
for (int x: set) {
arr[j++] = x;
}
return k;
}
}
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.*;
public class Main {
public static void main(String[] args) {
int arr[] = {1,1,2,2,2,3,3};
int k = removeDuplicates(arr);
System.out.println("The array after removing duplicate elements is ");
for (int i = 0; i < k; i++) {
System.out.print(arr[i] + " ");
}
}
static int removeDuplicates(int[] arr) {
int i = 0;
for (int j = 1; j < arr.length; j++) {
if (arr[i] != arr[j]) {
i++;
arr[i] = arr[j];
}
}
return i + 1;
}
}
Question 5
Left Rotate an Array by One
Given an array ‘arr’ containing ‘n’ elements, rotate this array left once and return it.
Rotating the array left by one means shifting all elements by one place to the left and moving the first element to the last position in the array.
Example:
Input: ‘a’ = 5, ‘arr’ = [1, 2, 3, 4, 5]
Output: [2, 3, 4, 5, 1]
Explanation: We moved the 2nd element to the 1st position, and 3rd element to the 2nd position, and 4th element to the 3rd position, and the 5th element to the 4th position, and move the 1st element to the 5th position.
Detailed explanation ( Input/output format, Notes, Images )
Sample input 1:
4
5 7 3 2
Sample output 1:
7 3 2 5
Explanation of sample input 1:
Move the first element to the last and rest all the elements to the left.
Sample input 2:
5
4 0 3 2 5
Sample output 2:
0 3 2 5 4
Explanation of sample input 2:
Same as sample input 1, Move the first element to the last and rest all the elements to the left
Expected time complexity:
O( n ), Where ‘n’ is the size of an input array ‘arr’.
Constraints :
1 <= ‘n’ <= 10^5
1 <= 'arr[i] <= 10^9
Time Limit: 1 sec
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
iimport java.util. * ;
class Test {
static void solve(int arr[], int n) {
int temp[] = new int[n];
for (int i = 1; i < n; i++) {
temp[i - 1] = arr[i];
}
temp[n - 1] = arr[0];
for (int i = 0; i < n; i++) {
System.out.print(temp[i] + " ");
}
}
public static void main(String args[]) {
int n = 5;
int arr[] = {
1,
2,
3,
4,
5
};
solve(arr, n);
}
}
Question 6
Rotate array
Given an array ‘arr’ with ‘n’ elements, the task is to rotate the array to the left by ‘k’ steps, where ‘k’ is non-negative.
Example:
'arr '= [1,2,3,4,5]
‘k’ = 1 rotated array = [2,3,4,5,1]
‘k’ = 2 rotated array = [3,4,5,1,2]
‘k’ = 3 rotated array = [4,5,1,2,3] and so on.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
8
7 5 2 11 2 43 1 1
2
Sample Output 1:
2 11 2 43 1 1 7 5
Explanation of Sample Input 1:
Rotate 1 steps to the left: 5 2 11 2 43 1 1 7
Rotate 2 steps to the left: 2 11 2 43 1 1 7 5
Sample Input 2:
4
5 6 7 8
3
Sample Output 2:
8 5 6 7
Explanation of Sample Input 2:
Rotate 1 steps to the left: 6 7 8 5
Rotate 2 steps to the left: 7 8 5 6
Rotate 2 steps to the left: 8 5 6 7
Expected Time Complexity:
O(n), where ‘n’ is the size of the array ‘arr’ and ‘k’ is the number of rotations.
Constraints:
1 <= ‘n’ <= 10^3
1 <= ‘arr’[i] <= 10^9
1 <= ‘k’ < ‘n’
Better Approach
For Rotating Elements to left
Step 1: Reverse the first k elements of the array
Step 2: Reverse the last n-k elements of the array.
Step 3: Reverse the whole array.
For Eg , arr[]={1,2,3,4,5,6,7} , k=2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
public class Main {
// Function to Reverse the array
public static void Reverse(int[] arr, int start, int end) {
while (start <= end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
// Function to Rotate k elements to left
public static void Rotateeletoleft(int[] arr, int n, int k) {
// Reverse first k elements
Reverse(arr, 0, k - 1);
// Reverse last n-k elements
Reverse(arr, k , n - 1);
// Reverse whole array
Reverse(arr, 0, n - 1);
}
public static void main(String args[]) {
int[] arr = {1,2,3,4,5,6,7};
int n = 7;
int k = 2;
Rotateeletoleft(arr, n, k);
System.out.print("After Rotating the k elements to left ");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
Question 7
Move Zero’s to End
Given an array ‘arr’ of ‘n’ non-negative integers, your task is to move all the zeros to the end of the array while keeping the non-zero elements at the start of the array in their original order. Return the modified array.
Example :
Input: ‘n’ = 5, ‘arr’ = [1, 2, 0, 0, 2, 3]
Output: [1, 2, 2, 3, 0, 0]
Explanation: Moved all the 0’s to the end of an array, and the rest of the elements retain the order at the start.
Detailed explanation ( Input/output format, Notes, Images )
Sample input 1:
4
0 0 0 1
Sample output 1:
1 0 0 0
Explanation of sample input 1:
Output: [1, 0, 0, 0]
We move all the 0’s to the end of an array, and the rest of the elements retained the order at the start.
Sample input 2:
5
4 0 3 2 5
Sample output 2:
4 3 2 5 0
Explanation of sample input 2:
Output: [4, 3, 2, 5, 0]
we move all the 0’s to the end of an array, and the rest of the elements retained the order at the start.
Expected time complexity:
The expected time complexity is O(n).
Constraints:
1 ≤ n ≤ 10^6
0 ≤ arr[i] ≤ 10^9
Time limit: 1 sec
Brute Force Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util. * ;
public class Test {
public static int[] moveZeros(int n, int[] a) {
//temporary array:
ArrayList < Integer > temp = new ArrayList < >();
//copy non-zero elements
//from original -> temp array:
for (int i = 0; i < n; i++) {
if (a[i] != 0) temp.add(a[i]);
}
// number of non-zero elements.
int nz = temp.size();
//copy elements from temp
//fill first nz fields of
//original array:
for (int i = 0; i < nz; i++) {
a[i] = temp.get(i);
}
//fill rest of the cells with 0:
for (int i = nz; i < n; i++) {
a[i] = 0;
}
return a;
}
public static void main(String[] args) {
int[] arr = {
1,
0,
2,
3,
2,
0,
0,
4,
5,
1
};
int n = 10;
int[] ans = moveZeros(n, arr);
for (int i = 0; i < n; i++) {
System.out.print(ans[i] + " ");
}
System.out.println("");
}
}
Better Approach
Step 1 :- a[i] != 0 so we will swap a[i] and a[j] and move both the pointers by 1.
Step 2 :- a[i] != 0, so we will again swap a[i] and a[j] and move both the pointers by 1 This process will continue until i crosses n-1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util. * ;
public class Test {
public static int[] moveZeros(int n, int[] a) {
int j = 0;
//Move the pointers i and j
//and swap accordingly:
for (int i = j + 1; i < n; i++) {
if (a[i] != 0) {
//swap a[i] & a[j]:
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
j++;
}
}
return a;
}
public static void main(String[] args) {
int[] arr = {
1,
0,
2,
3,
2,
0,
0,
4,
5,
1
};
int n = 10;
int[] ans = moveZeros(n, arr);
for (int i = 0; i < n; i++) {
System.out.print(ans[i] + " ");
}
System.out.println("");
}
}
Question 8
Merge 2 Sorted Array
Given two sorted arrays, ‘a’ and ‘b’, of size ‘n’ and ‘m’, respectively, return the union of the arrays.
The union of two sorted arrays can be defined as an array consisting of the common and the distinct elements of the two arrays. The final array should be sorted in ascending order.
Note: ‘a’ and ‘b’ may contain duplicate elements, but the union array must contain unique elements.
Example:
Input: ‘n’ = 5 ‘m’ = 3
‘a’ = [1, 2, 3, 4, 6]
‘b’ = [2, 3, 5]
Output: [1, 2, 3, 4, 5, 6]
Explanation: Common elements in ‘a’ and ‘b’ are: [2, 3]
Distinct elements in ‘a’ are: [1, 4, 6]
Distinct elements in ‘b’ are: [5]
Union of ‘a’ and ‘b’ is: [1, 2, 3, 4, 5, 6]
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1 :
5 3
1 2 3 4 6
2 3 5
Sample Output 1 :
1 2 3 4 5 6
Explanation Of Sample Input 1 :
Input: ‘n’ = 5 ‘m’ = 3
‘a’ = [1, 2, 3, 4, 6]
‘b’ = [2, 3, 5]
Output: [1, 2, 3, 4, 5, 6]
Explanation: Common elements in ‘a’ and ‘b’ are: [2, 3]
Distinct elements in ‘a’ are: [1, 4, 6]
Distinct elements in ‘b’ are: [5]
Union of ‘a’ and ‘b’ is: [1, 2, 3, 4, 5, 6]
Sample Input 2:
4 3
1 2 3 3
2 2 4
Sample Output 2:
1 2 3 4
Explanation Of Sample Input 2 :
Input: ‘n’ = 5 ‘m’ = 3
‘a’ = [1, 2, 3, 3]
‘b’ = [2, 2, 4]
Output: [1, 2, 3, 4]
Explanation: Common elements in ‘a’ and ‘b’ are: [2]
Distinct elements in ‘a’ are: [1, 3]
Distinct elements in ‘b’ are: [4]
Union of ‘a’ and ‘b’ is: [1, 2, 3, 4]
Expected Time Complexity:
O(( N + M )), where ‘N’ and ‘M’ are the sizes of Array ‘A’ and ‘B’.
Constraints :
1 <= ‘n’, ‘m’ <= 10^5
-10^9 <= ‘a’[i], ‘b’[i] <= 10^9
Time Limit: 1 sec
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
package org.practice.cpdsa.array.important;
import org.practice.cpdsa.sorting.Helper;
public class MergeTwoSortedArray {
public static void main(String[] args) {
int[] oneSortedArray = new int[]{ 1, 4, 7, 8, 10};
int[] twoSortedArray = new int[]{ 2, 3, 9 };
mergeTwoSortedArray(oneSortedArray, twoSortedArray);
mergeTwoSortedArrayGAP(oneSortedArray, twoSortedArray, oneSortedArray.length, twoSortedArray.length);
Helper.print(oneSortedArray);
Helper.print(twoSortedArray);
}
private static int nextGap(int gap) {
if(gap <= 1) {
return 0;
}
return (gap / 2) + (gap % 2);
}
// here we will find gap from length and swap gap elements
// here j - n taking and i - n taking for second array because it starts from 0 and
// here one time 4 , 2, 1 gap will be there and if we increase in inner loop i and j by 1 then gap will be maintained
// as j already point to gap and write acc. to j
private static void mergeTwoSortedArrayGAP(int[] oneSortedArray, int[] twoSortedArray, int n, int m) {
int gap = nextGap(n + m);
while(gap > 0) {
int i = 0;
int j = gap;
while (j < (n + m)) {
if (j < n && oneSortedArray[i] > oneSortedArray[j]) {
int temp = oneSortedArray[i];
oneSortedArray[i] = oneSortedArray[j];
oneSortedArray[j] = temp;
} else if (j >= n && i < n && oneSortedArray[i] > twoSortedArray[j - n]) {
int temp = oneSortedArray[i];
oneSortedArray[i] = twoSortedArray[j - n];
twoSortedArray[j - n] = temp;
} else if (j >= n && i >= n && twoSortedArray[i - n] > twoSortedArray[j - n]) {
int temp = twoSortedArray[i - n];
twoSortedArray[i - n] = twoSortedArray[j - n];
twoSortedArray[j - n] = temp;
}
j++;
i++;
}
gap = nextGap(gap);
}
}
// here we will sort second array and swap the data from first array to second array.
// time complexity O(n*m)
private static void mergeTwoSortedArray(int[] oneSortedArray, int[] twoSortedArray) {
for(int i = 0; i <= oneSortedArray.length - 1; i++) {
if(twoSortedArray[0] < oneSortedArray[i]) {
int temp = oneSortedArray[i];
oneSortedArray[i] = twoSortedArray[0];
twoSortedArray[0] = temp;
sortTheArray(twoSortedArray);
}
}
}
private static void sortTheArray(int[] twoSortedArray) {
for(int j = 0; j < twoSortedArray.length - 1; j++) {
if(twoSortedArray[j] > twoSortedArray[j + 1]) {
int temp = twoSortedArray[j];
twoSortedArray[j] = twoSortedArray[j + 1];
twoSortedArray[j + 1] = temp;
}
}
}
}
Question 9
Find the missing number in an array
Problem Statement: Given an integer N and an array of size N-1 containing N-1 numbers between 1 to N. Find the number(between 1 to N), that is not present in the given array.
Example 1:
Input Format: N = 5, array[] = {1,2,4,5}
Result: 3
Explanation: In the given array, number 3 is missing. So, 3 is the answer.
Example 2:
Input Format: N = 3, array[] = {1,3}
Result: 2
Explanation: In the given array, number 2 is missing. So, 2 is the answer.
Brute Force Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util. * ;
public class Test {
public static int missingNumber(int[] a, int N) {
//Summation of first N numbers:
int sum = (N * (N + 1)) / 2;
//Summation of all array elements:
int s2 = 0;
for (int i = 0; i < N - 1; i++) {
s2 += a[i];
}
int missingNum = sum - s2;
return missingNum;
}
public static void main(String args[]) {
int N = 5;
int a[] = {
1,
2,
4,
5
};
int ans = missingNumber(a, N);
System.out.println("The missing number is: " + ans);
}
}
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util. * ;
public class Test {
public static int missingNumber(int[] a, int N) {
int xor1 = 0,
xor2 = 0;
for (int i = 0; i < N - 1; i++) {
xor2 = xor2 ^ a[i]; // XOR of array elements
xor1 = xor1 ^ (i + 1); //XOR up to [1...N-1]
}
xor1 = xor1 ^ N; //XOR up to [1...N]
return (xor1 ^ xor2); // the missing number
}
public static void main(String args[]) {
int N = 5;
int a[] = {
1,
2,
4,
5
};
int ans = missingNumber(a, N);
System.out.println("The missing number is: " + ans);
}
}
Question 10
Count Maximum Consecutive One’s in the array
Problem Statement: Given an array that contains only 1 and 0 return the count of maximum consecutive ones in the array.
Examples:
Example 1:
Input: prices = {1, 1, 0, 1, 1, 1}
Output: 3
Explanation: There are two consecutive 1’s and three consecutive 1’s in the array out of which maximum is 3.
Input: prices = {1, 0, 1, 1, 0, 1}
Output: 2
Explanation: There are two consecutive 1’s in the array.
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class Main {
static int findMaxConsecutiveOnes(int nums[]) {
int cnt = 0;
int maxi = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
cnt++;
} else {
cnt = 0;
}
maxi = Math.max(maxi, cnt);
}
return maxi;
}
public static void main(String args[]) {
int nums[] = { 1, 1, 0, 1, 1, 1 };
int ans = findMaxConsecutiveOnes(nums);
System.out.println("The maximum consecutive 1's are " + ans);
}
}
Question 11
Find The Single Element
You are given a sorted array ‘arr’ of positive integers of size ‘n’.
It contains each number exactly twice except for one number, which occurs exactly once.
Find the number that occurs exactly once.
Example :
Input: ‘arr’ = {1, 1, 2, 3, 3, 4, 4}.
Output: 2
Explanation: 1, 3, and 4 occur exactly twice. 2 occurs exactly once. Hence the answer is 2.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
5
1 1 2 2 3
Sample Output 1:
3
Explanation of sample output 1:
{1, 2} each occurs twice, whereas 3 occurs only once.
Hence the answer is 3.
Sample Input 2:
5
8 8 9 9 10
Sample Output 2:
10
Expected time complexity :
The expected time complexity is O(n), but try solving it in O(log n).
Constraints:
1 <= ‘n’ <= 10^4
1 <= ‘arr[i]’ <= 10^9
‘n’ is always odd.
Time Limit: 1 sec
Brute Force Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;
public class Test {
public static int getSingleElement(int []arr) {
// Size of the array:
int n = arr.length;
//Run a loop for selecting elements:
for (int i = 0; i < n; i++) {
int num = arr[i]; // selected element
int cnt = 0;
//find the occurrence using linear search:
for (int j = 0; j < n; j++) {
if (arr[j] == num)
cnt++;
}
// if the occurrence is 1 return ans:
if (cnt == 1) return num;
}
//This line will never execute
//if the array contains a single element.
return -1;
}
public static void main(String args[]) {
int[] arr = {4, 1, 2, 1, 2};
int ans = getSingleElement(arr);
System.out.println("The single element is: " + ans);
}
}
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;
public class tUf {
public static int getSingleElement(int []arr) {
//size of the array:
int n = arr.length;
// Declare the hashmap.
// And hash the given array:
HashMap<Integer, Integer> mpp = new HashMap<>();
for (int i = 0; i < n; i++) {
int value = mpp.getOrDefault(arr[i], 0);
mpp.put(arr[i], value + 1);
}
//Find the single element and return the answer:
for (Map.Entry<Integer, Integer> it : mpp.entrySet()) {
if (it.getValue() == 1) {
return it.getKey();
}
}
//This line will never execute
//if the array contains a single element.
return -1;
}
public static void main(String args[]) {
int[] arr = {4, 1, 2, 1, 2};
int ans = getSingleElement(arr);
System.out.println("The single element is: " + ans);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util. * ;
public class Test {
public static int getSingleElement(int[] arr) {
//size of the array:
int n = arr.length;
// XOR all the elements:
int xorr = 0;
for (int i = 0; i < n; i++) {
xorr = xorr ^ arr[i];
}
return xorr;
}
public static void main(String args[]) {
int[] arr = {
4,
1,
2,
1,
2
};
int ans = getSingleElement(arr);
System.out.println("The single element is: " + ans);
}
}
Question 12
Longest Subarray With Sum K
You are given an array ‘a’ of size ‘n’ and an integer ‘k’.
Find the length of the longest subarray of ‘a’ whose sum is equal to ‘k’.
Example :
Input: ‘n’ = 7 ‘k’ = 3
‘a’ = [1, 2, 3, 1, 1, 1, 1]
Output: 3
Explanation: Subarrays whose sum = ‘3’ are:
[1, 2], [3], [1, 1, 1] and [1, 1, 1]
Here, the length of the longest subarray is 3, which is our final answer.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1 :
7 3
1 2 3 1 1 1 1
Sample Output 1 :
3
Explanation Of Sample Input 1 :
Subarrays whose sum = ‘3’ are:
[1, 2], [3], [1, 1, 1] and [1, 1, 1]
Here, the length of the longest subarray is 3, which is our final answer.
Sample Input 2 :
4 2
1 2 1 3
Sample Output 2 :
1
Sample Input 3 :
5 2
2 2 4 1 2
Sample Output 3 :
1
Expected time complexity :
The expected time complexity is O(n).
Constraints :
1 <= ‘n’ <= 5 * 10 ^ 6
1 <= ‘k’ <= 10^18
0 <= ‘a[i]’ <= 10 ^ 9
Time Limit: 1-second
Brute Force Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
public class Test {
public static int getLongestSubarray(int []a, int k) {
int n = a.length; // size of the array.
int len = 0;
for (int i = 0; i < n; i++) { // starting index
int s = 0;
for (int j = i; j < n; j++) { // ending index
// add the current element to
// the subarray a[i...j-1]:
s += a[j];
if (s == k)
len = Math.max(len, j - i + 1);
}
}
return len;
}
public static void main(String[] args) {
int[] a = { -1, 1, 1};
int k = 1;
int len = getLongestSubarray(a, k);
System.out.println("The length of the longest subarray is: " + len);
}
}
Better Approach
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class SlidingWindow {
public static void main(String[] args) {
int[] arr = new int[]{1,2,3,1,1,1,1};
int result = getTheMaximumLengthOfSubArray(arr, arr.length, 3);
System.out.println(result);
}
// time complexity :- O(2 * N)
private static int getTheMaximumLengthOfSubArray(int[] arr, int len, int k) {
int i = 0;
int j = 0;
int maxWindow = 0;
int sum = 0;
while(j < len) {
sum += arr[j];
if (sum == k) {
maxWindow = Math.max(maxWindow, j - i + 1);
} else {
while (sum > k) {
sum -= arr[i];
i++;
}
if (sum == k) {
maxWindow = Math.max(maxWindow, j - i + 1);
}
}
j++;
}
return maxWindow;
}
}
Question 13
You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
Example 1:
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
Example 2:
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
Example 3:
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
Constraints:
1 <= people.length <= 5 * 104
1 <= people[i] <= limit <= 3 * 104
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Arrays;
public class BoatToSavePeople {
public static void main(String[] args) {
System.out.println(numRescueBoats(new int[]{1, 2},3));
}
public static int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int i = 0;
int j = people.length - 1;
int count = 0;
while(i <= j){
if(people[i] + people[j] <= limit){
i++;
}
j--;
count++;
}
return count;
}
}
Question 14
Highest / Lowest Frequency Elements
Given an array ‘v’ of ‘n’ numbers.
Your task is to find and return the highest and lowest frequency elements.
If there are multiple elements that have the highest frequency or lowest frequency, pick the smallest element.
Example:
Input: ‘n’ = 6, ‘v’ = [1, 2, 3, 1, 1, 4]
Output: 1 2
Explanation: The element having the highest frequency is ‘1’, and the frequency is 3. The elements with the lowest frequencies are ‘2’, ‘3’, and ‘4’. Since we need to pick the smallest element, we pick ‘2’. Hence we return [1, 2].
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1 :
6
1 2 3 1 1 4
Sample Output 1 :
1 2
Sample Explanation 1:
Input: ‘n’ = 6, ‘v’ = [1, 2, 3, 1, 1, 4]
Output: 1 2
Explanation: The element having the highest frequency is ‘1’, and the frequency is 3. The elements with the lowest frequencies are ‘2’, ‘3’, and ‘4’. Since we need to pick the smallest element, we pick ‘2’. Hence we return [1, 2].
Sample Input 2 :
6
10 10 10 3 3 3
Sample Output 2 :
3 3
Sample Explanation 2:
Input: ‘n’ = 6, ‘v’ = [10, 10, 10, 3, 3, 3]
Output: 3 3
Explanation: Since the frequency of ‘3’ and ‘10’ is 3. Therefore, the element with the maximum and minimum frequency is ‘3’.
Expected Time Complexity :
The expected time complexity is O(n), where n is the size of the array.
Expected Space Complexity :
The expected time complexity is O(n), where n is the size of the array.
Constraints :
2 <= n <= 10^4
1 <= v[i] <= 10^9
There are at least two distinct elements in the array.
Time Limit: 1 sec
Brute Force Approach
1
Better Approach
1
Question 15
Count Frequency in a range
You are given an array ‘arr’ of length ‘n’ containing integers within the range ‘1’ to ‘x’.
Your task is to count the frequency of all elements from 1 to n.
Note:
You do not need to print anything. Return a frequency array as an array in the function such that index 0 represents the frequency of 1, index 1 represents the frequency of 2, and so on.
Example:
Input: ‘n’ = 6 ‘x’ = 9 ‘arr’ = [1, 3, 1, 9, 2, 7]
Output: [2, 1, 1, 0, 0, 0]
Explanation: Below Table shows the number and their counts, respectively, in the array
Number Count
1 2
2 1
3 1
4 0
5 0
6 0
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
6 4
1 3 4 3 4 1
Sample Output 1:
2 0 2 2 0 0
Explanation Of Sample Input 1 :
Frequency table:
Number Count
1 2
2 0
3 2
4 2
5 0
6 0
Sample Input 2 :
5 5
1 2 3 4 5
Sample Output 2 :
1 1 1 1 1
Explanation Of Sample Input 2 :
Frequency table:
Number Count
1 1
2 1
3 1
4 1
5 1
Constraints:
1 <= n <= 10^5
1 <= x <= 10^5
1 <= arr[i] <= x
Brute Force Approach
1
Better Approach
1
Question 16
Factorial Numbers Not Greater Than N
You are given an integer ’n’.
Your task is to return a sorted array (in increasing order) containing all the factorial numbers which are less than or equal to ‘n’.
The factorial number is a factorial of a positive integer, like 24 is a factorial number, as it is a factorial of 4.
Note:
In the output, you will see the array returned by you.
Example:
Input: ‘n’ = 7
Output: 1 2 6
Explanation: Factorial numbers less than or equal to ‘7’ are ‘1’, ‘2’, and ‘6’.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
7
Sample Output 1 :
1 2 6
Explanation Of Sample Input 1:
Input: ‘n’ = 7
Output: 1 2 6
Explanation: Factorial numbers less than or equal to ‘7’ are ‘1’, ‘2’, and ‘6’.
Sample Input 2:
2
Sample Output 2:
1 2
Explanation Of Sample Input 2:
Input: ‘n’ = 2
Output: 1 2
Explanation: Factorial numbers less than or equal to ‘2’ are ‘1’ and ‘2’.
Expected Time Complexity:
The expected time complexity is O(m), where ‘m’ is the number of factorial numbers which are less than or equal to ‘n’.
Expected Space Complexity:
The expected space complexity is O(m), where ‘m’ is the number of factorial numbers which are less than or equal to ‘n’.
Constraints:
1 <= n <= 10^18
Time Limit: 1-sec
Brute Force Approach
1
Better Approach
1
Question 17
Reverse an array
Given an array ‘arr’ of size ‘n’.
Return an array with all the elements placed in reverse order.
Note:
You don’t need to print anything. Just implement the given function.
Example:
Input: n = 6, arr = [5, 7, 8, 1, 6, 3]
Output: [3, 6, 1, 8, 7, 5]
Explanation: After reversing the array, it looks like this [3, 6, 1, 8, 7, 5].
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
8
3 1 1 7 4 2 6 11
Sample Output 1:
11 6 2 4 7 1 1 3
Explanation Of Sample Input 1 :
After reversing the array, it looks like this [11, 6, 2, 4, 7, 1, 1, 3].
Sample Input 2:
4
8 1 3 2
Sample Output 2:
2 3 1 8
Explanation Of Sample Input 2 :
After reversing the array, it looks like this [2, 3, 1, 8].
Expected time complexity
The expected time complexity is O(n).
Constraints:
1 <= ‘n’ <= 10^6
-10^9 <= ‘arr[i]’ <=10^9
Brute Force Approach
1
Better Approach
1
Question 18
Check Palindrome (recursive)
Determine if a given string ‘S’ is a palindrome using recursion. Return a Boolean value of true if it is a palindrome and false if it is not.
Note: You are not required to print anything, just implement the function. Example:
Input: s = “racecar”
Output: true
Explanation: “racecar” is a palindrome.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
abbba
Sample Output 1:
true
Explanation Of Sample Input 1 :
“abbba” is a palindrome
Sample Input 2:
abcd
Sample Output 2:
false
Explanation Of Sample Input 2 :
“abcd” is not a palindrome.
Constraints:
0 <= |S| <= 10^6
where |S| represents the length of string S.
Brute Force Approach
1
Better Approach
1
Question 19
Print Fibonacci Series
Given an integer ‘n’, return first n Fibonacci numbers using a generator function.
Example:
Input: ‘n’ = 5
Output: 0 1 1 2 3
Explanation: First 5 Fibonacci numbers are: 0, 1, 1, 2, and 3.
Note:
You don’t need to print anything. Just implement the given function.
Detailed explanation ( Input/output format, Notes, Images )
Sample Input 1:
5
Sample Output 1:
0 1 1 2 3
Explanation Of Sample Input 1:
The first 5 Fibonacci numbers are 0, 1, 1, 2, and 3.
Sample Input 2:
3
Sample Output 2:
0 1 1
Explanation Of Sample Input 2:
The first 5 Fibonacci numbers are 0, 1, 1.
Expected time complexity
The expected time complexity is O(n).
Constraints:
1 <= n <= 45
Time Limit: 1 s
Brute Force Approach
1
Better Approach
1