ARRAY || BASIC PROBLEMS Flashcards
1
Q
If you’re given an array like [10, 20, 30, 40, 50], how would you conceptually explain what “printing alternate elements” even means?
A
You start by printing the first element (index 0), then skip the next element (index 1), print the third element (index 2), skip the next, and continue like that until the end of the array.
2
Q
What pattern in the indices do you notice when you’re printing alternate elements? How does that help you plan the for loop?
A
The indices are 0, 2, 4, 6, etc., so the loop needs to start at index 0 and increment by 2 each time (i += 2) to print every alternate element.
3
Q
How would you write a for loop in JavaScript that prints every alternate element from an array starting at index 0? (✍🏽 Write the loop structure!)
A
for (let i = 0; i < arr.length; i += 2) {
console.log(arr[i]);
}
4
Q
Why do we do i += 2 instead of i++ in the loop when finding alternate elements?
A
We do i += 2 to skip every second element, so we’re only accessing elements at even indices (0, 2, 4, etc.), which gives us the alternate elements.
5
Q
What is the time complexity and the space complexity of the iterative solution for printing alternate elements of an array? And why?
A
Time Complexity: O(n), because we are iterating through the array once.
Space Complexity: O(1), because we’re not using any extra space for the iteration itself (just a few variables).
6
Q
If you’re using recursion instead of iteration for printing alternate elements of an array, how does your “jump to the next alternate element” happen inside the recursive function?
A
In recursion, you print the current element, then make a recursive call with index + 2 to jump to the next alternate element.
7
Q
In the recursive version for printing alternate elements of an array, what two key things happen in each call before making the next call?
A
You push the current element (based on index) into the result.
You call the recursive function with index + 2.
8
Q
Why does the recursive solution have O(n) space complexity even though the iterative one has O(1) space complexity for printing alternate elements of an array?
A
The recursive solution uses additional space for each recursive call in the call stack, which grows with the size of the array, resulting in O(n) space complexity. The iterative solution only uses a few variables, so it’s O(1).
9
Q
Write the skeleton of the recursive function that handles alternate element printing in JavaScript. (Don’t write the whole code, just the basic function signature and idea.)
A
function printAlternatesRecursive(arr, index) {
if (index < arr.length) {
console.log(arr[index]);
printAlternatesRecursive(arr, index + 2);
}
}
10
Q
Given this array: [-5, 1, 4, 2, 12], what should the output be when you print the alternate elements starting from index 0?
A
The output should be: -5 4 12
11
Q
If you had to explain the difference between the iterative and recursive approach for this for alternate elements to a friend who knows zero coding… what would you say in one sentence?
A
The iterative approach uses a for loop and updates the index manually, while the recursive approach calls the same function repeatedly with a new index, effectively jumping to the next alternate element.
12
Q
You are asked in an interview:
“Could you optimize your recursive solution for alternate elements to not use O(n) space?”
What would you say? 👀
A
Yes, you could convert the recursion into an iterative loop, which would use O(1) space instead of O(n) by eliminating the need for a call stack.
13
Q
What does it mean to “print alternate elements” of an array? Can you explain it like I’m a 5-year-old?
A
“Printing alternate elements” just means skipping every other element in the array. So, if you have an array like [10, 20, 30, 40, 50], you start by printing the first element (10), then skip the second element (20), then print the third element (30), skip the next (40), and print the fifth element (50). Basically, you’re just picking every odd-numbered position (0, 2, 4, etc.)
14
Q
What is the Linear Search Algorithm used for in an array? Explain it step by step.
A
Linear Search is used to find the first occurrence of an element in an array. Here’s how it works:
Start from the first element of the array.
Compare each element with the target element (x).
If you find the element, return its index.
If you don’t find the element after checking all elements, return -1 to indicate it’s not present.
For example, in the array [10, 2, 3, 4] and looking for 3:
Check 10 → No.
Check 2 → No.
Check 3 → Yes! Return index 2.
15
Q
Given the following JavaScript code, what will be the output for the array arr = [10, 8, 30] and x = 6?
function search(arr, n, x) {
for (let i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
let arr = [10, 8, 30];
let x = 6;
let n = arr.length;
let result = search(arr, n, x);
console.log(result);
A
The function will return -1 because 6 is not present in the array [10, 8, 30]. The output will be:
-1
16
Q
What is the time complexity of Linear Search in the best, worst, and average cases?
A
Best Case: O(1)
The element is at the first index, so it’s found immediately.
Worst Case: O(n)
The element is at the last index or not in the array at all, so all elements must be checked.
Average Case: O(n)
On average, half of the array will be searched before finding the element (or determining it’s not there).
17
Q
What are the time and space complexities of Linear Search?
A
Time Complexity:
Best Case: O(1)
Worst Case: O(n)
Average Case: O(n)
Space Complexity: O(1)
Linear Search doesn’t require extra memory, just a variable for iteration, so its space complexity is constant.
18
Q
When should you prefer Linear Search over more optimized search algorithms (like Binary Search)?
A
Linear Search is preferred when:
The array is unsorted, and you need to find an element.
The dataset is small, so performance isn’t an issue.
You’re searching in linked lists, where elements aren’t in contiguous memory.
19
Q
If the element x is not found in the array during a Linear Search, what does the algorithm return, and why?
A
If x is not found in the array, Linear Search returns -1. This indicates that the element does not exist in the array.
20
Q
What are the advantages and disadvantages of using Linear Search?
A
Advantages:
Can be used on unsorted arrays.
No need for extra memory.
Simple to implement.
Disadvantages:
Slow for large arrays (O(n) time complexity).
Not efficient for large datasets compared to algorithms like Binary Search.
21
Q
Given this code to search for x in an array arr[], what is the issue in the following function?
function search(arr, n, x) {
for (let i = 0; i <= n; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
A
The issue is with the loop condition. It should be i < n, not i <= n.
Correct code:
for (let i = 0; i < n; i++)
This is because i starts from 0 and should not exceed the last index (n-1), or else it will lead to an out-of-bounds error.
22
Q
How would you implement a recursive version of the Linear Search Algorithm?
A
Here’s a basic recursive implementation of Linear Search:
function searchRecursive(arr, index, x) {
if (index >= arr.length) return -1; // Base case: if index exceeds array length, return -1
if (arr[index] === x) return index; // If the element is found, return its index
return searchRecursive(arr, index + 1, x); // Recursive call for the next index
}
This function starts from index 0 and searches each element recursively until it finds the element or reaches the end of the array.
23
Q
Why is Linear Search often used with unsorted lists?
A
Linear Search is used with unsorted lists because it doesn’t require the list to be sorted. It checks every element one by one, making it the most straightforward way to search in an unsorted collection.
24
Q
What is the time complexity and space complexity of the iterative approach to finding the largest element in an array?
A
Time Complexity: O(n)
You traverse the array once, where n is the number of elements in the array.
Space Complexity: O(1)
The space used does not depend on the size of the array because you’re only storing the max value and an index during the iteration.
25
Here’s an example of an iterative approach to finding the largest element in an array. What will be the output for the array [10, 324, 45, 90, 9808]?
function largest(arr) {
let max = arr[0];
for (let i = 1; i < arr.length; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
const arr = [10, 324, 45, 90, 9808];
console.log(largest(arr));
The output will be 9808, which is the largest element in the array [10, 324, 45, 90, 9808].
26
What is the recursive approach to finding the largest element in an array, and how does it work?
The recursive approach works by breaking down the problem into smaller sub-problems:
If you're at the last element of the array, return that element.
For each step, compare the current element with the result of the recursive call on the rest of the array.
Return the maximum of the current element and the recursive result.
Time Complexity: O(n)
Space Complexity: O(n) (because of recursion stack)
27
Here’s a recursive function to find the largest element. What will be the output for the array [10, 324, 45, 90, 9808]?
function findMax(arr, i) {
if (i === arr.length - 1) {
return arr[i];
}
let recMax = findMax(arr, i + 1);
return Math.max(recMax, arr[i]);
}
function largest(arr) {
return findMax(arr, 0);
}
const arr = [10, 324, 45, 90, 9808];
console.log(largest(arr));
The output will be 9808. The recursive function will call itself until it reaches the last element, then it will return the maximum value.
28
How can you use built-in functions to find the largest element in an array?
In JavaScript, you can use Math.max(...arr) to find the largest element. The spread operator (...) unpacks the array into individual arguments for Math.max.
Example:
function largest(arr) {
return Math.max(...arr);
}
const arr = [10, 324, 45, 90, 9808];
console.log(largest(arr)); // Output: 9808
29
Compare the iterative, recursive, and library method approaches to finding the largest element in terms of time complexity, space complexity, and simplicity.
Iterative Approach:
Time Complexity: O(n)
Space Complexity: O(1)
Simplicity: Simple and easy to understand; no extra overhead.
Recursive Approach:
Time Complexity: O(n)
Space Complexity: O(n) (due to the recursion stack)
Simplicity: More complex due to recursion; harder to debug for larger arrays.
Library Method (Math.max):
Time Complexity: O(n)
Space Complexity: O(1)
Simplicity: Extremely simple and concise; most efficient for small datasets.
30
What are some edge cases to consider when finding the largest element in an array?
Array with one element: The only element is the largest.
Array with negative numbers: Make sure negative values are handled correctly.
Array with duplicate elements: The largest element should be returned, even if it's repeated multiple times.
Array with all equal elements: Any element can be considered the largest.
Empty array: Handle it gracefully, returning undefined or a specific error message (depending on how you want to handle it).
31
Can you optimize the recursive approach to have better space complexity?
Yes, the recursive approach uses O(n) space because of the recursion stack. You can optimize it by using the iterative approach, which uses O(1) space and achieves the same result.
32
What is the time complexity of finding the largest element in an array for each approach (Iterative, Recursive, and Library)?
Iterative Approach: O(n)
Recursive Approach: O(n)
Library Method: O(n)
All approaches traverse the entire array once, so their time complexity is linear.
33
How can you find the second largest element in an array using sorting?
Sort the array in non-decreasing order.
Traverse from the second last element backward.
Find the first element that is not equal to the largest element.
Return this as the second largest element. If no such element exists, return -1.
Time Complexity: O(n * log n) (due to sorting)
Space Complexity: O(1)
34
How does the Two Pass Search approach work to find the second largest element in an array?
First Pass: Traverse the array to find the largest element.
Second Pass: Traverse the array again to find the largest element that is not the largest found in the first pass.
Return this as the second largest element. If no second largest is found, return -1.
Time Complexity: O(n)
Space Complexity: O(1)
35
How do you find the second largest element using only one pass?
Initialize two variables: largest and secondLargest to -1.
Traverse the array once:
If the current element is larger than largest, update secondLargest to the old largest and largest to the current element.
If the current element is smaller than largest but larger than secondLargest, update secondLargest.
Return secondLargest or -1 if no second largest element is found.
Time Complexity: O(n)
Space Complexity: O(1)
36
What’s an example of finding the second largest element using sorting?
Array: [12, 35, 1, 10, 34, 1]
Sort the array: [1, 1, 10, 12, 34, 35]
Traverse from the second last element and find 34 as the second largest.
Output: 34
Time Complexity: O(n * log n)
Space Complexity: O(1)
37
How do you find the second largest element with Two Pass Search?
Array: [12, 35, 1, 10, 34, 1]
First pass: Find the largest element: 35
Second pass: Find the largest element that isn’t 35: 34
Output: 34
Time Complexity: O(n)
Space Complexity: O(1)
38
Can you show how to find the second largest element with One Pass Search?
Array: [12, 35, 1, 10, 34, 1]
Start with largest = -1 and secondLargest = -1.
Traverse:
12: Update largest = 12.
35: Update largest = 35, secondLargest = 12.
1: No change.
10: No change.
34: Update secondLargest = 34.
Output: 34
Time Complexity: O(n)
Space Complexity: O(1)
39
What happens if all elements in the array are the same when looking for the second largest?
If all elements are the same, there is no second largest element. Return -1.
Example:
Array: [10, 10, 10]
Output: -1
40
Write the code to find the second largest element in an array using sorting.
function getSecondLargest(arr) {
let n = arr.length;
// Sort the array in non-decreasing order
arr.sort((a, b) => a - b);
// Start from second last element as last element is the largest
for (let i = n - 2; i >= 0; i--) {
// Return the first element which is not equal to the largest element
if (arr[i] !== arr[n - 1]) {
return arr[i];
}
}
// If no second largest element was found, return -1
return -1;
}
// Driver Code
const arr = [12, 35, 1, 10, 34, 1];
console.log(getSecondLargest(arr)); // Output: 34
41
Write the code to find the second largest element in an array using the two-pass search method.
function getSecondLargest(arr) {
let n = arr.length;
let largest = -1, secondLargest = -1;
// Finding the largest element
for (let i = 0; i < n; i++) {
if (arr[i] > largest)
largest = arr[i];
}
// Finding the second largest element
for (let i = 0; i < n; i++) {
// Update second largest if the current element is greater
// than second largest and not equal to the largest
if (arr[i] > secondLargest && arr[i] !== largest) {
secondLargest = arr[i];
}
}
return secondLargest;
}
// Driver Code
let arr = [12, 35, 1, 10, 34, 1];
console.log(getSecondLargest(arr)); // Output: 34
42
Write the code to find the second largest element in an array using the one-pass search method.
function getSecondLargest(arr) {
const n = arr.length;
let largest = -1, secondLargest = -1;
// Finding the second largest element in one pass
for (let i = 0; i < n; i++) {
// If arr[i] > largest, update second largest with largest
// and largest with arr[i]
if (arr[i] > largest) {
secondLargest = largest;
largest = arr[i];
}
// If arr[i] < largest and arr[i] > second largest,
// update second largest with arr[i]
else if (arr[i] < largest && arr[i] > secondLargest) {
secondLargest = arr[i];
}
}
return secondLargest;
}
// Driver Code
const arr = [12, 35, 1, 10, 34, 1];
console.log(getSecondLargest(arr)); // Output: 34
43
What does it mean to find the "largest three distinct elements" in an array? Why should we focus on distinct elements?
The goal is to find the three largest unique numbers in the array. If the array has fewer than three distinct numbers, return the available distinct numbers in descending order. We focus on distinct elements because duplicates don't count toward the top three largest numbers.
44
How would you find the largest three distinct elements using the naive solution (three traversals)?
What is the time complexity of this approach?
In the naive approach:
Traverse the array to find the first largest element.
In the second traversal, find the second largest (excluding the largest).
In the third traversal, find the third largest (excluding the first two).
Time complexity: O(n^2) (due to repeated traversal of the array for each element).
45
How can we find the top three largest distinct elements in one pass through the array?
Write the code for the efficient solution where you track the first, second, and third largest elements in one traversal.
function get3largest(arr) {
let fst = -Infinity, sec = -Infinity, thd = -Infinity;
arr.forEach(x => {
// If current element is greater than fst
if (x > fst) {
thd = sec;
sec = fst;
fst = x;
}
// If x is between fst and sec
else if (x > sec && x !== fst) {
thd = sec;
sec = x;
}
// If x is between sec and thd
else if (x > thd && x !== sec && x !== fst) {
thd = x;
}
});
let res = [];
if (fst !== -Infinity) res.push(fst);
if (sec !== -Infinity) res.push(sec);
if (thd !== -Infinity) res.push(thd);
return res;
}
// Driver code
let arr = [12, 13, 1, 10, 34, 1];
let res = get3largest(arr);
console.log(res.join(' '));
46
In the efficient solution, how do you make sure you don’t count duplicates when finding the largest, second largest, and third largest elements?
What is the logic to avoid counting the same element more than once?
To handle duplicates, you need to ensure that when updating the second or third largest values, they are not equal to the first or second largest values. This is done by checking if the current element is different from the largest or second largest before updating.
47
What is the definition of a "leader" in an array? Provide an example.
A leader is an element that is greater than or equal to all the elements to its right in the array. The rightmost element is always a leader.
For example, in the array [16, 17, 4, 3, 5, 2], the leaders are [17, 5, 2].
48
How does the naive approach work to find leaders in an array? What is the time complexity of this approach?
In the naive approach, we use two loops:
The outer loop picks each element from left to right.
The inner loop checks if the current element is greater than all the elements to its right.
If it is, it's a leader and is added to the result.
Time Complexity: O(n^2) due to the nested loops.
49
Explain how the efficient approach works to find leaders in an array using the "Suffix Maximum" technique. What is the time complexity of this approach?
The efficient approach scans the array from right to left:
Start with the rightmost element, which is always a leader.
As we move left, we track the maximum value (maxRight).
If the current element is greater than or equal to maxRight, it’s a leader, and we update maxRight.
Time Complexity: O(n) because we only traverse the array once.
50
Write the code to find the leaders in an array using the efficient "Suffix Maximum" approach. Ensure the leaders are printed in the correct order.
// Function to find the leaders in an array
function leaders(arr)
{
const result = [];
const n = arr.length;
// Start with the rightmost element
let maxRight = arr[n - 1];
// Rightmost element is always a leader
result.push(maxRight);
// Traverse the array from right to left
for (let i = n - 2; i >= 0; i--) {
if (arr[i] >= maxRight) {
maxRight = arr[i];
result.push(maxRight);
}
}
// Reverse the result array to maintain
// original order
result.reverse();
return result;
}
// Driver code
const arr = [ 16, 17, 4, 3, 5, 2 ];
const result = leaders(arr);
console.log(result.join(" "));
Output
17 5 2
Illustration:
arr[] = {16, 17, 4, 3, 5, 2}
Initially : maxRight = 2, res[] = { 2 }
i = 4, maxRight = 5, res[] = { 2, 5 }
i= 3, maxRight = 5, res[] = { 2, 5 }
i = 2, maxRight = 5, res[] = { 2, 5 }
i = 1, maxRight = 17, res[] = { 2, 5, 17 }
i = 0, maxRight = 17, res[] = { 2, 5, 17 }
Reverse res[] = {17, 5, 2} and return
51
In the efficient approach, how do you maintain the correct order of leaders when traversing the array from right to left?
Since we're traversing from right to left, we need to reverse the result array at the end. This will restore the original order of the leaders as we would have identified them starting from the rightmost element.
52
What should the output be if the input array is empty? Write the code to handle this case.
If the array is empty, there are no elements to consider, so the output should be an empty array [].
53
What does it mean for an array to be sorted in ascending order? Provide an example of a sorted and unsorted array.
An array is sorted in ascending order if each element is less than or equal to the one that follows it.
For example, the array [20, 21, 45, 89, 89, 90] is sorted, while the array [20, 20, 78, 98, 99, 97] is not because 97 is smaller than 99.
54
Explain the iterative approach to checking if an array is sorted. What is the time complexity?
Traverse the array starting from the second element.
For each element, check if it is smaller than or equal to the previous element.
If any element is found that is smaller than its predecessor, return false.
If no such element is found, return true (the array is sorted).
Time Complexity: O(n) because we only need to traverse the array once.
55
How does the recursive approach check if an array is sorted? What is the time complexity?
The base case checks if the array size is 1 or 0, returning true since a single element or an empty array is sorted.
Compare the last two elements. If the last element is greater than or equal to the one before it, recursively check the rest of the array.
If at any point an element is smaller than the one before it, return false.
Time Complexity: O(n) because we check each element once, but it uses O(n) space due to the recursion call stack.
56
Write the code to check if an array is sorted in ascending order using the iterative approach. Make sure the array includes equal consecutive elements.
// JavaScript program Iterative approach to check if an
// Array is sorted or not
// Function that returns true if array is
// sorted in non-decreasing order.
function arraySortedOrNot(arr, n)
// Array has one or no element
if (n === 0 || n === 1) {
return true;
}
for (let i = 1; i < n; i++) {
// Unsorted pair found
if (arr[i - 1] > arr[i]) {
return false;
}
}
// No unsorted pair found
return true;
}
// Driver Code
let arr = [20, 23, 23, 45, 78, 88];
let n = arr.length;
if (arraySortedOrNot(arr, n)) {
console.log("Yes");
} else {
console.log("No");
}
57
Why is the check for consecutive equal elements important in this problem? How does it affect the output?
Consecutive equal elements do not affect the sorted order, so they should be allowed. For example, in the array [20, 20, 45, 89, 89, 90], the repeated 20 and 89 do not disrupt the ascending order. The check ensures that as long as the current element is not smaller than the previous element, the array remains sorted.
58
What should the output be if the input array has only one element? Write the code to handle this case.
If the array has only one element, it is automatically sorted because there are no other elements to compare it to. The output should be Yes.
59
Write the code to check if an array is sorted in ascending order using the recursive approach
// JavaScript Recursive approach to check if an
// Array is sorted or not
// Function that returns true if array is
// sorted in non-decreasing order.
function arraySortedOrNot(a, n) {
// Base case
if (n == 1 || n == 0) {
return true;
}
// Check if present index and index
// previous to it are in correct order
// and rest of the array is also sorted
// if true then return true else return
// false
return a[n - 1] >= a[n - 2] && arraySortedOrNot(a, n - 1);
}
// Driver code
let arr = [20, 23, 23, 45, 78, 88];
let n = arr.length;
// Function Call
if (arraySortedOrNot(arr, n)) {
console.log("Yes");
} else {
console.log("No");
}
60
What do we mean by removing duplicates from a sorted array, and what is the output?
Removing duplicates means eliminating all repeated elements in a sorted array, leaving only one instance of each distinct element. The output is an array of unique elements, and we also return the length of this array.
61
How does the hash set approach work for removing duplicates, and what is its time and space complexity?
The hash set approach stores each element in a set as we traverse the array. If the element is not in the set, we add it to the result array.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n) because we use additional space for the hash set.
62
How can we optimize the solution for a sorted array to remove duplicates, and what is the time and space complexity?
Since the array is sorted, we can just compare each element with the previous one. If it's different, we move it to the next position in the array. This saves space and is efficient.
Time Complexity: O(n) because we traverse the array once.
Space Complexity: O(1) because no extra space is used except for the index tracking.
63
Write the code to remove duplicates from a sorted array using the optimized approach.
function removeDuplicates(arr) {
const n = arr.length;
if (n <= 1) return n;
let idx = 1; // Start from the second element
for (let i = 1; i < n; i++) {
if (arr[i] !== arr[i - 1]) {
arr[idx++] = arr[i]; // Place the distinct element
}
}
return idx; // Length of the array with unique elements
}
How it works:
Since the array is sorted, duplicates will always be consecutive. We can use two pointers:
One pointer (let's call it idx) keeps track of where the next distinct element should be placed.
The other pointer (i) goes through each element, checking if it's different from the previous one. If it is, we place it in the idx position.
Time Complexity: O(n)
Space Complexity: O(1) because we don’t use any extra space for storing elements.
64
What should happen if the input array contains only one element, and how should the code handle this?
If the array has only one element, it's already unique, so the function should return the array as it is. The length will be 1, and no changes are needed.
65
What should the output be if all elements in the array are the same, and how should the code handle this?
If all elements are the same, the output should be the array containing only one element. The function should detect that all elements are duplicates and only keep the first one.
66
Write the code to remove duplicates from a sorted array using a Hash Set (O(n) Time, O(n) Space)
How it works:
Use a hash set (or dictionary) to store elements as you traverse the array. If an element is not in the hash set, add it and store it in the result array.
function removeDuplicates(arr) {
const s = new Set();
let idx = 0;
for (let i = 0; i < arr.length; i++) {
if (!s.has(arr[i])) {
s.add(arr[i]);
arr[idx++] = arr[i];
}
}
return idx; // Length of the array with unique elements
}
Time Complexity: O(n)
Space Complexity: O(n) because of the hash set storing all unique elements.
67
What is a subarray, and how is it different from a substring?
A subarray is a contiguous portion of an array, whereas a substring is a contiguous portion of a string. Both are similar in that they involve contiguous sequences, but subarrays operate on arrays and substrings operate on strings.
68
How does the iterative approach work to generate all subarrays, and what are the time and space complexities?
In the iterative approach, two nested loops are used to pick all pairs of starting and ending indices, and for each pair, the subarray is printed.
Time Complexity: O(n^3)
Space Complexity: O(n) (for temporarily storing the subarray during printing).
69
How does the recursive approach work to generate all subarrays, and what are the time and space complexities?
In the recursive approach, two pointers (start and end) are used to generate subarrays. The recursion moves to the next subarray once the current one is printed.
Time Complexity: O(n^2), as there are n(n+1)/2 subarrays to generate.
Space Complexity: O(n), due to the recursion stack.
70
Write the code to generate all subarrays using the iterative approach.
To generate all subarrays, you need to iterate over the array twice:
The outer loop picks the starting index of the subarray.
The inner loop picks the ending index of the subarray (from the current starting index).
For each pair of starting and ending indices, the subarray is generated and printed.
function subArray(arr) {
const n = arr.length;
// Pick starting point
for (let i = 0; i < n; i++) {
// Pick ending point
for (let j = i; j < n; j++) {
// Print subarray between current starting and ending points
let subarr = [];
for (let k = i; k <= j; k++) {
subarr.push(arr[k]);
}
console.log(subarr.join(" "));
}
}
}
const arr = [1, 2, 3, 4];
console.log("All Non-empty Subarrays:");
subArray(arr);
Output:
All Non-empty Subarrays
1
1 2
1 2 3
1 2 3 4
2
2 3
2 3 4
3
3 4
4
Time Complexity: O(n^3)
Space Complexity: O(n), as we store subarrays temporarily for printing.
71
Write the code to generate all subarrays using the recursive approach.
The recursive approach involves using two pointers (start and end) to traverse the array.
If the end pointer reaches the end of the array, the recursion stops.
If start is greater than end, the recursion moves to the next subarray.
We print the subarray formed by the start and end pointers.
code:
function printSubArrays(arr, start, end) {
if (end == arr.length)
return;
// Increment the end point and start from 0
else if (start > end)
printSubArrays(arr, 0, end + 1);
// Print the subarray and increment the starting point
else {
let subArray = "[";
for (let i = start; i < end; i++) {
subArray += arr[i] + ", ";
}
subArray += arr[end] + "]";
console.log(subArray);
printSubArrays(arr, start + 1, end);
}
return;
}
var arr = [1, 2, 3];
printSubArrays(arr, 0, 0);
output:
[1]
[1, 2]
[2]
[1, 2, 3]
[2, 3]
[3]
Time Complexity: O(n^2), because we generate n(n+1)/2 subarrays.
Space Complexity: O(n) due to the recursion stack.
72
What should happen when the input array is empty, and how should the code handle this?
When the array is empty, no subarrays should be generated. The function should return without printing anything.
73
How do you reverse an array using a temporary array in JavaScript?
Create a temporary array of the same size as the original.
Copy elements from the original array to the temporary array in reverse order.
Copy the reversed elements from the temporary array back to the original array.
function reverseArray(arr) {
let n = arr.length;
let temp = new Array(n);
for (let i = 0; i < n; i++)
temp[i] = arr[n - i - 1];
for (let i = 0; i < n; i++)
arr[i] = temp[i];
}
const arr = [1, 4, 3, 2, 6, 5];
reverseArray(arr);
console.log(arr.join(" "));
74
Explain the two-pointer approach to reverse an array.
Initialize two pointers: one at the beginning (left) and one at the end (right) of the array.
Swap the elements at the two pointers.
Move the left pointer to the right and the right pointer to the left.
Repeat until the left pointer is greater than or equal to the right pointer.
function reverseArray(arr) {
let left = 0, right = arr.length - 1;
while (left < right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
const arr = [1, 4, 3, 2, 6, 5];
reverseArray(arr);
console.log(arr.join(" "));
75
How can you reverse an array by swapping elements in JavaScript?
Iterate over the first half of the array.
Swap each element with its corresponding element from the end.
Continue until you reach the middle of the array.
function reverseArray(arr) {
let n = arr.length;
for (let i = 0; i < n / 2; i++) {
let temp = arr[i];
arr[i] = arr[n - i - 1];
arr[n - i - 1] = temp;
}
}
const arr = [1, 4, 3, 2, 6, 5];
reverseArray(arr);
console.log(arr.join(" "));
76
How can you reverse an array using recursion in JavaScript?
Base case: If the array has one or zero elements, return it.
Swap the first and last elements.
Recursively call the function for the remaining subarray (exclude the first and last elements).
function reverseArrayRec(arr, l, r) {
if (l >= r) return;
[arr[l], arr[r]] = [arr[r], arr[l]];
reverseArrayRec(arr, l + 1, r - 1);
}
function reverseArray(arr) {
let n = arr.length;
reverseArrayRec(arr, 0, n - 1);
}
const arr = [1, 4, 3, 2, 6, 5];
reverseArray(arr);
console.log(arr.join(" "));
77
how do you reverse an array using JavaScript’s reverse() method?
Use the reverse() method on the array.
It reverses the elements in-place.
function reverseArray(arr) {
arr.reverse();
}
const arr = [1, 4, 3, 2, 6, 5];
reverseArray(arr);
console.log(arr.join(" "));
78
What is the time and space complexity of the naive array reversal approach using a temporary array?
Time Complexity: O(n)
Space Complexity: O(n) (due to the extra array)
79
What is the time and space complexity of the two-pointer approach for reversing an array?
Time Complexity: O(n)
Space Complexity: O(1) (no extra space used)
80
What is the time and space complexity of reversing an array by swapping elements?
Time Complexity: O(n)
Space Complexity: O(1) (in-place reversal)
81
What is the time and space complexity of the recursive array reversal approach?
Time Complexity: O(n)
Space Complexity: O(n) (due to the recursion stack)
82
What is the time and space complexity of the inbuilt reverse() method in JavaScript?
Time Complexity: O(n)
Space Complexity: O(1) (reverses in place)
83
How do you rotate an array to the right by d positions using the one-by-one method?
(Write the code)
function rotateRight(arr, d) {
const n = arr.length;
for (let i = 0; i < d; i++) {
let temp = arr[n - 1];
for (let j = n - 1; j > 0; j--) {
arr[j] = arr[j - 1];
}
arr[0] = temp;
}
}
84
What’s the time complexity of the one-by-one array rotation method, and why is it inefficient?
Time complexity: O(n * d). This is inefficient because for each of the d rotations, you are shifting all n elements, resulting in a nested loop. If d is large, it becomes even slower.
85
How do you rotate an array using a temporary array?
(Write the code)
function rotateWithTempArray(arr, d) {
const n = arr.length;
const temp = arr.slice(n - d); // Take the last d elements
for (let i = n - 1; i >= d; i--) {
arr[i] = arr[i - d]; // Shift elements to the right
}
for (let i = 0; i < d; i++) {
arr[i] = temp[i]; // Place the temp elements in the front
}
}
86
What is the time and space complexity of rotating an array using a temporary array?
Time complexity: O(n)
Space complexity: O(d) because we use a temporary array of size d.
87
What is the Juggling Algorithm, and how does it work to rotate an array?
(Write the code)
function rotateJuggling(arr, d) {
const n = arr.length;
const g = gcd(d, n); // Find greatest common divisor of d and n
for (let i = 0; i < g; i++) {
let temp = arr[i];
let j = i;
while (true) {
let k = j + d;
if (k >= n) k -= n;
if (k === i) break;
arr[j] = arr[k];
j = k;
}
arr[j] = temp;
}
}
88
How does the Juggling Algorithm improve efficiency over the one-by-one method of rotating an array?
The Juggling Algorithm improves efficiency by using the GCD (Greatest Common Divisor) to break the array into smaller groups, thus reducing the number of shifts. It requires O(n) time and no extra space for the rotation.
89
How do you rotate an array using the Reversal Algorithm?
(Write the code)
function rotateReversal(arr, d) {
const n = arr.length;
d = d % n; // Handle if d is larger than n
reverse(arr, 0, n - 1);
reverse(arr, 0, d - 1);
reverse(arr, d, n - 1);
}
function reverse(arr, start, end) {
while (start < end) {
let temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
90
Why is the Reversal Algorithm considered space-efficient for array rotation?
The Reversal Algorithm is space-efficient because it rotates the array in-place without using any extra space, except for a few variables. Its space complexity is O(1).
91
How can you rotate an array left by d positions using the right rotation method?
(Write the code)
function rotateLeftByRight(arr, d) {
const n = arr.length;
d = d % n; // Handle if d is larger than n
rotateRight(arr, n - d); // Rotate right by n-d
}
92
How do you calculate the new index of an element in a rotated array?
For right rotation, the new index of an element at index i will be (i + d) % n, where d is the number of rotations and n is the array length.
For left rotation, the new index will be (i - d + n) % n.
93
What would happen if you rotate an array of length n by n or more positions?
Rotating an array of length n by n positions will result in the same array because every element would just return to its original position. If d > n, then d % n gives the equivalent smaller rotation number.
94
How can you reduce the number of rotations when d > n?
By using the formula d = d % n, you can reduce the number of rotations. This ensures you don't rotate more than necessary and simplifies the problem.
95
What’s the formula to find the new index after rotating an element right by d positions?
The formula for the new index after right rotation is:
newIndex = (currentIndex + d) % n
96
How would you optimize left rotations by using right rotations?
To rotate left by d positions, rotate right by n - d positions instead. This reduces the problem to using the right rotation code.
97
What’s the difference between rotating an array to the left and to the right?
Left rotation moves elements to the left and shifts the rest to the right.
Right rotation moves elements to the right and shifts the rest to the left.
98
How do you handle cases where the number of rotations d is equal to or greater than the array length n?
You can reduce d by calculating d % n. This ensures you only rotate the array by the necessary number of positions, avoiding unnecessary rotations.
99
How would you write code to rotate an array left by d positions using the right rotation method?
(Write the code)
function rotateLeftByRight(arr, d) {
const n = arr.length;
d = d % n; // Handle if d is larger than n
rotateRight(arr, n - d); // Rotate right by n-d
}
100
What is the Naive approach to move all zeros to the end of an array?
The Naive approach involves creating a temporary array where non-zero elements are copied, followed by filling the remaining spots with zeros. Finally, the elements from the temporary array are copied back to the original array.
101
Write the code to move all zeros to the end using a temporary array in JavaScript.
function pushZerosToEnd(arr) {
const n = arr.length;
const temp = new Array(n);
let j = 0;
for (let i = 0; i < n; i++) {
if (arr[i] !== 0) {
temp[j++] = arr[i];
}
}
while (j < n)
temp[j++] = 0;
for (let i = 0; i < n; i++)
arr[i] = temp[i];
}
102
How does the Better Approach (Two Traversals) work to move zeros to the end?
In this approach, we traverse the array twice. The first traversal shifts non-zero elements to the front, while the second traversal fills the remaining spots with zeros.
103
Write the code for the Two Traversals approach to move zeros to the end in JavaScript.
function pushZerosToEnd(arr) {
let count = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0)
arr[count++] = arr[i];
}
while (count < arr.length)
arr[count++] = 0;
}
104
What is the Expected Approach (One Traversal) for moving zeros to the end?
The One Traversal approach uses a pointer (count) to track where the next non-zero element should go. If a non-zero element is found, it’s swapped with the element at the count index. This way, zeros are pushed to the end while traversing only once.
105
Write the code to move zeros to the end using One Traversal in JavaScript
function pushZerosToEnd(arr) {
let count = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] !== 0) {
[arr[i], arr[count]] = [arr[count], arr[i]];
count++;
}
}
}
106
What is the time and space complexity of the Naive approach (using a temporary array) to move zeros to the end of an array?
Time Complexity: O(n) (because we traverse the array twice).
Space Complexity: O(n) (due to the extra space used for the temporary array).
107
What is the time and space complexity of the Better Approach (Two Traversals) to move zeros to the end of an array?
Time Complexity: O(n) (because we traverse the array twice).
Space Complexity: O(1) (since we use the input array itself to store the result).
108
: What is the time and space complexity of the Expected Approach (One Traversal) to move zeros to the end of an array?
Time Complexity: O(n) (because we traverse the array once).
Space Complexity: O(1) (since we modify the array in-place).
109
What is the advantage of using the One Traversal approach to move zeros to the end?
The One Traversal approach is the most efficient because it only requires a single pass through the array, making it both time and space efficient (O(n) time, O(1) space).
110
What would happen if there were no zeros in the array when using the Two Traversals approach to move zeros to the end of an array?
If there are no zeros, the first traversal will shift all non-zero elements to the front, and the second traversal won’t change anything since count will be equal to the array length, leaving the array unchanged.
111
If the array contains only zeros, how would the code behave in the One Traversal approach to move zeros to the end of an array?
If the array contains only zeros, the count pointer would never increment, and no swaps would happen, so the array would remain filled with zeros.
112
What is the problem "Minimum Increment by k Operations to Make All Equal" asking you to do in terms of array manipulation?
The problem asks you to find the number of operations needed to make all elements of the array equal by incrementing the elements by a value k. If it's not possible, you should return -1.
113
What condition must be true for it to be possible to make all elements equal using k increments in the "Minimum Increment by k Operations to Make All Equal" problem?
For it to be possible to make all elements equal, the difference between any two elements must be divisible by k. That is, (max - arr[i]) % k == 0 for each element arr[i].
114
What does the algorithm do in the first step in the "Minimum Increment by k Operations to Make All Equal" problem?
The first step of the algorithm is to find the maximum element in the array (max). This will be the target value we want to equalize all other elements to.
115
What happens if the difference between an element and the maximum element is not divisible by k in the "Minimum Increment by k Operations to Make All Equal" problem?
If the difference between any element and the maximum element is not divisible by k, then it’s impossible to make all elements equal using k increments, and the algorithm should return -1.
116
How do you calculate the number of operations needed to make each element equal to the maximum element in the "Minimum Increment by k Operations to Make All Equal" problem?
For each element, the number of operations required to make it equal to the maximum element is calculated as (max - arr[i]) / k.
117
What is the time complexity of the solution to the "Minimum Increment by k Operations to Make All Equal" problem?
The time complexity of this solution is O(n), where n is the number of elements in the array, because the algorithm loops through the array twice (once to find the maximum and once to calculate operations).
118
What is the space complexity of the solution to the "Minimum Increment by k Operations to Make All Equal" problem?
The space complexity of this solution is O(1) because it only uses a few variables for computation and does not require any extra space proportional to the input size.
119
What is the final step in the algorithm for the "Minimum Increment by k Operations to Make All Equal" problem?
The final step is to return the result res, which is the total number of operations needed to make all elements equal to the maximum element.
120
Write the JavaScript function to solve the "Minimum Increment by k Operations to Make All Equal" problem.
function minOps(arr, n, k) {
var max = arr[0];
for(var i=0; i max)
max = arr[i];
}
var res = 0;
for (var i = 0; i < n; i++) {
if ((max - arr[i]) % k != 0)
return -1;
else
res += (max - arr[i]) / k;
}
return res;
}
var arr = [ 21, 33, 9, 45, 63 ];
var n = arr.length;
var k = 6;
document.write(minOps(arr, n, k));
121
What is the expected output for the input arr = [21, 33, 9, 45, 63] and k = 6 in the "Minimum Increment by k Operations to Make All Equal" problem?
The expected output is 24, as it requires 24 operations to make all elements equal by incrementing them by 6.
122
What is the problem "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" asking you to do?
The problem asks you to reduce an array of integers to a single element by repeatedly selecting a pair, removing the larger of the two, and paying a cost equal to the value of the smaller one. The goal is to find the minimum total cost of these operations.
123
What is the cost of each operation in the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem?
The cost of each operation is equal to the value of the smaller element in the selected pai
124
How can you minimize the total cost in the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem?
To minimize the total cost, you should always remove the larger element in each pair, and the smallest element in the array should be used in each operation because it will minimize the cost.
125
What is the formula for calculating the minimum total cost in the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem?
The formula for calculating the minimum total cost is:
(size of array - 1) * minimum element in the array.
126
How do you calculate the minimum total cost in the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem?
To calculate the minimum total cost, find the minimum element in the array and multiply it by (n - 1), where n is the size of the array.
127
What is the time complexity of the solution to the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem?
The time complexity is O(n) because you only need to find the minimum element in the array once.
128
What is the space complexity of the solution to the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem?
The space complexity is O(1) because you only need a constant amount of extra space to compute the result.
129
Write the JavaScript function to solve the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem.
function cost(a) {
// Minimum cost is (size - 1) multiplied with minimum element.
const n = a.length;
return (n - 1) * Math.min(...a);
}
const a = [4, 3, 2];
console.log(cost(a)); // Output: 4
130
What is the expected output for the input arr = [4, 3, 2] in the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem?
The expected output is 4, because the minimum cost is obtained by removing 4 and 3, which results in a total cost of 2 + 2 = 4.
131
What is the expected output for the input arr = [3, 4] in the "Minimum Cost to Make Array Size 1 by Removing Larger of Pairs" problem?
The expected output is 3, because the minimum cost is obtained by removing 4, and the cost is 3.
