arrays Flashcards
1
Q
what are the two ways of creating arrays in js
A
literal using square brackets [] and using new Array()
2
Q
what is an array constructor?
A
The “Array Constructor” refers to a method of creating arrays by invoking the Array constructor function aka new array()
3
Q
what are some differences between using the [] and new array()
A
[] is usually faster more readable and used more and when you do
let array = [3]; it will create an array with the value 3 only
while with using array constructor
let array = new array(5) ; it will create an array with 5 slots with no values so its usually better for creating an array with a specific size
4
Q
how can you access the last and first values
assigning them to a name
A
let array = [1, 2, 3] ;
let firstInArray = array[0] -> access the value in index 0 which is first
let lastInArray = array[array.length - 1] -> array.length -1 give last in array since index count starts from 0 not 1
5
Q
how can you modify or overwrite a value in an array
A
first you access the value you want to modify then overwrite it
array[3] = “new value”;
6
Q
what does these do
push()
unshift()
pop()
shift()
A
push() to add at the end on an array
unshift() to add at the beginning on an array
pop() to remove at the end
shift() to remove from the beggining
7
Q
how does slice() work
A
The slice() method of Array instances returns a shallow copy of a portion of an array into a new array object selected from start to end
const animals = [“ant”, “bison”, “camel”, “duck”, “elephant”];
console.log(animals.slice(2));
// Expected output: Array [“camel”, “duck”, “elephant”]
console.log(animals.slice(2, 4));
// Expected output: Array [“camel”, “duck”]
8
Q
How can you increase or decrease an array length
A
Let array = [1, 2,3,4];
To increase
array.length = 5 -> [1,2,3,4,emptyslot]
To decrease
array.length = 2 -> [1,2]
9
Q
Array are fundamental to build _____
A
Other data structures
10
Q
What are some way to iterate an array
A
Using a for loop
let a = [10, 20, 30, 40, 50];
for (let item of a) {
console.log(item);
Using forEach()
let a = [10, 20, 30, 40, 50];
a.forEach((item) => {
console.log(item);
});
11
Q
How can you combine 2 arrays
A
Using concat() which returns a new array
const array1 = [“a”, “b”, “c”];
const array2 = [“d”, “e”, “f”];
const array3 = array1.concat(array2);
console.log(array3);
// Expected output: Array [“a”, “b”, “c”, “d”, “e”, “f”
12
Q
Does toString() work on an array if so what does it do
A
Yes, it turns an array into a string
Let array =[“hello”, “dear”]
Console.log( array.toString() );
13
Q
How can you check if sometjing is an array in js
There are three methods tell me which works and which doesnt
A
Let ourarray= [1,2,3,4];
Typeof(ourarray) doesnt work on an array it returns a object
Array.isArray() works
Console.log(Array.isArray(ourarray) ); returns true
Instanceof works
Console.log ( ourarray instanceof Array ); returns true
14
Q
WHAT DOES “EVERY-NTH ELEMENT” “EVERY-Kth ELEMENT”
MEAN?
A
Let’s say we got an array like:
[5, 10, 15, 20, 25, 30, 35]
Every 1st element: [5, 10, 15, 20, 25, 30, 35] (no skipping)
Every 2nd element: [5, 15, 25, 35] (we skip 1 each time)
Every 3rd element: [5, 20, 35] (we skip 2 each time)
Every 4th element: [5, 25]
See the pattern? You pick an element, then skip some, then pick again.
15
Q
How do you print every alternate (every 2nd) element of an array using a loop?
A
for (let i = 0; i < arr.length; i += 2) {
console.log(arr[i]);
}
16
Q
How do you recursively print every alternate element in an array?
A
function printAlternates(arr, i = 0) {
if (i >= arr.length) return;
console.log(arr[i]);
printAlternates(arr, i + 2);
}
17
Q
How do you create a new array of every 3rd element using a loop?
A
let res = [];
for (let i = 2; i < arr.length; i += 3) {
res.push(arr[i]);
}
18
Q
How do you recursively get every 3rd element and return them as a new array?
A
function getEveryThird(arr, i = 2, res = []) {
if (i >= arr.length) return res;
res.push(arr[i]);
return getEveryThird(arr, i + 3, res);
}
19
Q
How do you double every 2nd element of an array using a loop?
A
for (let i = 1; i < arr.length; i += 2) {
arr[i] *= 2;
}
20
Q
How do you recursively double every 2nd element in-place?
A
function doubleEverySecond(arr, i = 1) {
if (i >= arr.length) return;
arr[i] *= 2;
doubleEverySecond(arr, i + 2);
}
21
Q
What’s the basic structure of a recursive function that processes an array?
A
function recurse(arr, i = 0) {
if (i >= arr.length) return;
// do something with arr[i]
recurse(arr, i + k); // k = how much you want to skip
}
22
Q
What’s the generic pattern to loop through an array by steps of k from index s?
A
for (let i = s; i < arr.length; i += k) {
// arr[i]
}
23
Q
When is recursion better than a loop?
A
When the problem is naturally recursive (e.g. trees, backtracking)
When you want cleaner code for problems that branch
When you’re flexin’ on interviews
24
Q
What happens if you forget the base case in recursion?
A
You cause a stack overflow and crash your program. Always add:
if (i >= arr.length) return;
25
What is the Time and Space Complexity of printing alternate elements of an array using a loop?
Time Complexity: O(n)
(n = total number of elements, but we still loop once through every other item)
Space Complexity: O(1)
(no extra space used if we’re just printing)
26
What is the Time and Space Complexity of printing/storing alternate elements using recursion?
Time Complexity: O(n)
(function still touches every other element, but same total runtime as loop)
Space Complexity: O(n)
(because each recursive call adds a layer to the call stack, even if we’re not storing results)
27
What is the Time and Space Complexity of printing alternate elements of an array using a loop?
Time Complexity: O(n)
(n = total number of elements, but we still loop once through every other item)
Space Complexity: O(1)
(no extra space used if we’re just printing)
28
If you store alternate elements in a new array using a loop, what’s the space complexity?
Space Complexity: O(n/k) → simplified as O(n)
(since in Big O, constants don’t matter)
29
What is a Linear Search?
Checking each element one by one in an array until the target is found.
30
Linear search time complexity (best, worst, avg)?
Best: O(1) (found first)
Worst: O(n) (found last or not at all)
Average: O(n)
31
Linear search Space complexity?
O(1) — we are not using any extra space
32
When should I use linear search?
Small datasets
Unsorted data
Linked lists
You want simplicity
33
Why recursion can be worse sometimes for linear search?
It uses stack space. On big arrays, you might hit a stack overflow
34
How can you write linear search in code using loop
function linearSearch(arr, x) {
for (let i = 0; i < arr.length; i++) {
// Check if the current element equals the target value (x)
if (arr[i] === x) {
return i; // If we find the element, return the index
}
}
return -1; // If we go through the whole array and don’t find it, return -1
}
// Example:
const arr = [1, 2, 3, 4];
const target = 3;
const result = linearSearch(arr, target);
console.log(result); // Output: 2 (the index where 3 is located)
35
Why is using a for loop better than foreach() for linear search
forEach is nice, but:
You can’t return or break early. So if you find the item early on, you’re still forced to keep looping through the whole array.
It’s less efficient for early exits.
You have to use a lil workaround (like setting a separate index var), which makes the code less clean and harder to read.
36
What is a Linear Search and how does it work?
Linear Search is a simple algorithm that checks every element in an array to find a target element. If the target element is found, it returns the index of the first occurrence; otherwise, it returns -1.
37
How would you write a Linear Search using a loop to find the number x in an array arr?
function linearSearch(arr, x) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === x) {
return i; // Return index of the element
}
}
return -1; // Element not found
}
38
Why do we use a for loop in a Linear Search?
We use a for loop to iterate over each element of the array, comparing each element with the target (x). The loop continues until the target is found or all elements are checked.
39
Can you use break in a Linear Search loop? What happens if you do?
Yes, you can use break to exit the loop early when the target element is found. However, return is more effective because it immediately stops the function and gives the result.
function linearSearch(arr, x) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === x) {
console.log(`Found at index ${i}`);
break; // Exits the loop, but function keeps running
}
}
}
Note: return is generally used instead of break for better control.
40
How would you implement a Linear Search using recursion?
function linearSearchRec(arr, x, index = 0) {
if (index === arr.length) {
return -1; // Base case: element not found
}
if (arr[index] === x) {
return index; // Found, return index
}
return linearSearchRec(arr, x, index + 1); // Recurse to next element
}
41
What are the advantages and disadvantages of using recursion for Linear Search?
Pros:
• Recursive code can be cleaner and more elegant for smaller problems.
• It breaks down the problem into smaller subproblems.
Cons:
• Recursion can lead to stack overflow for very large arrays due to function call overhead.
• It’s generally less efficient compared to using a loop in terms of memory usage.
42
Should you use iteration or recursion for Linear Search? When is one better than the other?
Use iteration for most cases because it’s more efficient and avoids the overhead of function calls in recursion.
Use recursion for cleaner, more readable code in small or educational contexts, where performance isn’t a big concern.
43
Can Linear Search work on unsorted arrays?
Yes, Linear Search works on unsorted arrays. Unlike binary search, it doesn’t require sorting. It checks every element in sequence, making it applicable for both sorted and unsorted data.
44
What is the time complexity of Linear Search?
Best Case: O(1) if the element is found at the first index.
Worst Case: O(n) if the element is not found or is at the last index.
Average Case: O(n) since each element must be checked.
Space Complexity: O(1) for iterative, and O(n) for recursive (due to the call stack).
45
How can you improve the performance of Linear Search?
You can’t improve the time complexity of Linear Search because it checks each element, meaning it will always take O(n) time. However, if the array is sorted or if additional structure (like hashing) is used, you could use a different search method (e.g., binary search for sorted arrays or hash tables for constant-time lookups).
46
Can Linear Search be used on data structures other than arrays?
Yes, Linear Search can be applied to linked lists and other sequential data structures (like strings) as long as you can access the elements one by one.
47
What is the time complexity of the iterative approach for finding the largest element in an array?
O(n)
48
What is the space complexity of the iterative approach for finding the largest element in an array?
O(1)
49
In the iterative approach for finding the largest element, what is the initial value of ‘max’?
arr[0]
50
How does the recursive approach to find the largest element work?
It traverses the array recursively and compares the current element with the maximum found from the rest of the array.
51
What is the time complexity of the recursive approach to find the largest element in an array?
O(n)
52
What is the space complexity of the recursive approach to find the largest element in an array?
O(n)
53
In the recursive approach, what is the base case?
The base case is when the index ‘i’ reaches the last element in the array.
54
What method is used in the library-based approach to find the largest element in an array?
Math.max(…arr)
55
What is the time complexity of the library-based approach to find the largest element in an array?
O(n)
56
What is the space complexity of the library-based approach to find the largest element in an array?
O(1)
57
What does the ‘…’ operator do in the library-based approach?
It spreads the elements of the array so that Math.max can compare them individually.
58
What is the main idea of the Iterative Approach for finding the largest element in an array?
Traverse the entire array from the beginning.
Start by assuming the first element is the largest.
Compare each subsequent element with the current largest element and update if a larger number is found.
59
With finding the largest value in an array What is the initial value assigned to max in the Iterative Approach? Why?
max is initially assigned the value of the first element in the array (arr[0]).
This is because we need a starting point to compare all other elements against.
60
Why do we start the loop from index 1 in the Iterative Approach of finding largest number in an array?
We start the loop from index 1 because we’ve already considered the first element as the initial maximum.
There’s no need to check the first element again.
61
What is the condition used to update the max value during the loop for finding the largest number in an array ?
The condition is: if (arr[i] > max)
This checks if the current element is larger than the current max. If it is, we update max.
62
While trying to find largest value What happens when we finish looping through the array?
Once the loop finishes, we return the value stored in max, which is the largest element in the array.
63
What is the time and space complexity of the Iterative Approach for finding largest value in an array?
Time Complexity: O(n), where n is the number of elements in the array.
This is because we only need to check each element once.
Space Complexity: O(1), because we only need one extra variable (max) to keep track of the largest element. No additional memory is required.
64
How do you implement the iterative approach in code to find the largest element in an array?
function largest(arr) {
let max = arr[0]; // Start by assuming the first element is the largest
// Loop through the rest of the array
for (let i = 1; i < arr.length; i++) {
if (arr[i] > max) { // If we find a larger number
max = arr[i]; // Update max
}
}
return max; // Return the largest number
}
console.log(largest([10, 324, 45, 90, 9808])); // Output: 9808
65
What happens if all elements in the array are the same when using the iterative approach for ginding the largest value in an array?
If all elements are the same, the loop will finish without updating max and the function will return the first element of the array, as it was initially set to max.
66
While trying to find the largest value in an array
How does the iterative approach handle negative numbers in the array?
The iterative approach works the same for negative numbers. It compares each element and updates max whenever a larger number (including negative numbers) is found.
67
What happens if the array is empty when using the iterative approach to find the largest element?
The code would break because arr[0] doesn’t exist. You would need to handle an empty array by returning something like undefined or "Array is empty"
68
What is an example of a situation where the iterative approach to finding the largest element is better than using recursion?
The iterative approach is better when you want lower memory usage because recursion requires more memory due to the call stack. In the iterative approach, we use only one extra variable (max), making it more efficient for simple tasks.
69
Can we use the forEach loop to implement the iterative approach to find the largest element?
Yes, you can use forEach to loop through the array and compare each element with max, but forEach doesn’t support breaking out of the loop. Here’s an example of how you can do it:
function largest(arr) {
let max = arr[0]; // Assume the first element is the largest
arr.forEach(value => {
if (value > max) {
max = value; // Update max if current value is larger
}
});
return max; // Return the largest value
}
70
What would happen if you accidentally start the loop at index 0 instead of index 1 in the iterative approach for finding largest value?
If you start the loop at index 0, the loop will compare the first element to itself, which is unnecessary. The result would still be correct, but it’s not efficient.
71
What happens if the array has only one element in the iterative approach for finding largest value in an array?
If there’s only one element, the function will return that element, because it’s both the first and largest (the only element).
72
What is the key difference between the Iterative Approach and the Recursive Approach to finding the largest element in an array?
The Iterative Approach uses a loop to go through each element in the array, whereas the Recursive Approach uses function calls to go through the array step by step.
73
How does the recursive function begin when finding the largest element in the array?
The recursive function starts by checking if we’ve reached the last element in the array (i === arr.length - 1). If we are at the last element, we return that element as the base case.
74
How does the recursive function compare elements to find the largest value in the array?
The recursive function compares the current element (arr[i]) to the largest element found from the rest of the array by calling itself recursively with the next index (i + 1). The larger value between arr[i] and the result of the recursive call is returned.
75
What is the role of the base case in the recursive function for finding the largest value in an array?
The base case checks if the current index (i) is the last index in the array. If true, the function simply returns the element at that index as the largest value, stopping further recursion.
76
What happens after the recursive call returns when finding the largest element in the array?
After the recursive call returns, the function compares the element at index i (arr[i]) with the maximum value returned from the rest of the array (recMax). It then returns the larger of the two values, which helps in finding the largest element in the array.
77
How does the recursive function go through the entire array?
The function makes recursive calls by increasing the index (i + 1) in each call, effectively moving through the entire array one element at a time until the base case is reached.
78
What is the time complexity of the Recursive Approach for finding the largest element in an array?
The time complexity is O(n) because the function has to traverse the array once, making a recursive call for each element.
79
What is the space complexity of the Recursive Approach for finding the largest element in an array?
The space complexity is O(n) because each recursive call adds a new frame to the call stack, and the recursion goes as deep as the number of elements in the array.
80
How do you implement the Recursive Approach to find the largest element in an array?
function findMax(arr, i) {
// Base case: When we reach the last index, return that element
if (i === arr.length - 1) {
return arr[i];
}
// Recursively find the maximum of the rest of the array
let recMax = findMax(arr, i + 1);
// Compare with the current element and return the larger one
return Math.max(recMax, arr[i]);
}
function largest(arr) {
return findMax(arr, 0); // Start from the first index
}
console.log(largest([10, 324, 45, 90, 9808])); // Output: 9808
81
What happens if the array has only one element when finding the largest value recursively?
If the array has only one element, the function immediately reaches the base case and returns that element as the largest value, since no other elements exist to compare it to.
82
How does the Recursive Approach handle arrays with negative numbers when finding the largest element?
The Recursive Approach works the same way for negative numbers. It compares each element and finds the largest value, which could be a negative number, by comparing the current element to the largest value in the rest of the array.
83
What happens if the array is empty when trying to find the largest value using recursion?
If the array is empty, the function will cause an error because it tries to access an element that doesn’t exist. To prevent this, you should check for an empty array before starting the recursion.
84
What is the main advantage of the Recursive Approach to finding the largest element in an array?
The recursive approach simplifies the problem into smaller subproblems, making the code elegant and easy to understand, especially for problems like these where the array can be broken down into smaller parts.
85
Can you optimize the Recursive Approach to reduce space complexity when finding the largest value in an array?
While you can optimize the recursive approach by using tail recursion (which JavaScript doesn’t optimize well), converting it into an Iterative Approach can eliminate the extra stack frames, reducing space complexity to O(1).
86
What happens if you don’t handle the base case properly in the Recursive Approach when finding the largest element in an array?
If the base case is not correctly handled, the function will recurse infinitely, leading to a stack overflow error because it will never reach the end of the array.
87
What’s the fastest and laziest way to find the largest value in a JS array?
Using Math.max(...arr) — spread the array and let Math handle it.
88
What does the ... (spread operator) do in Math.max(...arr)?
It unpacks the array values into individual arguments.
Example: [10, 20, 30] becomes 10, 20, 30.
89
Why can’t we just do Math.max(arr)?
Because Math.max expects numbers, not an array. Math.max([1, 2, 3]) gives NaN.
90
What’s the time and space complexity of match.max(…array) ?
Time: O(n) (still checks every number).
Space: O(1) (no new data structures).
91
When should you use the math.max(…arr) method?
When you don’t wanna code the logic yourself and just need the biggest number.
92
Write a function in JavaScript that finds the largest number in the array [12, 99, 3, 47] using the built-in Math.max() method.
function findLargest(arr) {
return Math.max(...arr);
}
const arr = [12, 99, 3, 47];
console.log(findLargest(arr)); // Output: 99
93
What does …array do exactly ? And whats the … called
Spread operator
The spread operator ... takes all the values from the array and spreads them out as individual numbers.
94
What does the naive approach to finding the second largest element in an array do first?
It sorts the array in descending order and picks the first element that’s different from the max.
95
Time complexity of the naive sort-based approach?
O(n log n) because sorting takes that long.
96
In the naive approach, what edge case should you check after sorting?
If all elements are equal or there's only one distinct element
97
What's the two-pass method for finding the second largest?
First pass: find the max. Second pass: find the largest number that’s not equal to the max.
98
Time complexity of the two-pass approach for finding the second largest?
O(n) — two linear passes through the array.
99
What's the logic behind the one-pass solution for second largest?
Track max and secondMax in one loop: if a number is bigger than max, update both. If it’s between them, update secondMax
100
What values should max and secondMax start with?
-Infinity, to make sure any number replaces them at first.
101
What should you return if there is no second largest element?
Return -1 or a message saying “only one distinct number”
102
In the one-pass method for three largest, what 3 variables do you track?
first, second, and third largest elements.
103
In the one-pass method for three largest, What’s the update rule when a new number is bigger than first?
Set third = second, second = first, and first = x.
104
Write a function to find the second largest element in this array using the sorting method:
[12, 35, 1, 10, 34, 1]
function secondLargest(arr) {
let unique = [...new Set(arr)];
if (unique.length < 2) return -1;
unique.sort((a, b) => b - a);
return unique[1];
}
console.log(secondLargest([12, 35, 1, 10, 34, 1])); // 34
105
Write code to find the second largest value using two traversals on this array:
[10, 5, 10]
function secondLargest(arr) {
let max = Math.max(...arr);
let second = -Infinity;
for (let num of arr) {
if (num !== max && num > second) {
second = num;
}
}
return second === -Infinity ? -1 : second;
}
console.log(secondLargest([10, 5, 10])); // 5
106
Write a function to find the second largest number in a single pass on this array:
[2, 3, 1, 4, 4]
function secondLargest(arr) {
let max = -Infinity;
let second = -Infinity;
for (let num of arr) {
if (num > max) {
second = max;
max = num;
} else if (num > second && num !== max) {
second = num;
}
}
return second === -Infinity ? -1 : second;
}
console.log(secondLargest([2, 3, 1, 4, 4])); // 3
107
Write a function to find the top 3 largest distinct numbers in a single pass using this array:
[12, 13, 1, 10, 34, 1]
function get3largest(arr) {
let fst = -Infinity, sec = -Infinity, thd = -Infinity;
arr.forEach(x => {
if (x > fst) {
thd = sec;
sec = fst;
fst = x;
} else if (x > sec && x !== fst) {
thd = sec;
sec = x;
} 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;
}
console.log(get3largest([12, 13, 1, 10, 34, 1])); // [34, 13, 12]
108
Use the efficient method to find top 3 distinct numbers in:
[10, 10, 10]
function get3largest(arr) {
let fst = -Infinity, sec = -Infinity, thd = -Infinity;
arr.forEach(x => {
if (x > fst) {
thd = sec;
sec = fst;
fst = x;
} else if (x > sec && x !== fst) {
thd = sec;
sec = x;
} 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;
}
console.log(get3largest([10, 10, 10])); // [10]
109
Write JavaScript code to find all leaders in the array [10, 3, 5, 2, 8, 1] using the nested loop method (O(n²) time).
An element is a leader if no element to its right is greater than it.
function findLeaders(arr) {
const result = [];
const n = arr.length;
for (let i = 0; i < n; i++) {
let isLeader = true;
for (let j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
isLeader = false;
break;
}
}
if (isLeader) result.push(arr[i]);
}
return result;
}
console.log(findLeaders([10, 3, 5, 2, 8, 1])); // Output: [10, 8, 1]
110
Write a function to find leaders in [7, 10, 4, 10, 6, 5, 2] using the optimal approach with right-to-left traversal. Time should be O(n).
function findLeaders(arr) {
const result = [];
let maxRight = arr[arr.length - 1];
result.push(maxRight);
for (let i = arr.length - 2; i >= 0; i--) {
if (arr[i] >= maxRight) {
maxRight = arr[i];
result.push(maxRight);
}
}
return result.reverse();
}
console.log(findLeaders([7, 10, 4, 10, 6, 5, 2])); // Output: [10, 10, 6, 5, 2]
111
Which elements are leaders in the array [9, 8, 7, 6, 5]? Write a function using the optimized method.
function leaders(arr) {
const result = [];
let maxRight = arr[arr.length - 1];
result.push(maxRight);
for (let i = arr.length - 2; i >= 0; i--) {
if (arr[i] >= maxRight) {
maxRight = arr[i];
result.push(maxRight);
}
}
return result.reverse();
}
console.log(leaders([9, 8, 7, 6, 5])); // Output: [9, 8, 7, 6, 5]
112
Write a function using the nested loop method to find the leaders in [1, 2, 3, 4, 0]. Why is 0 still a leader?
function leaders(arr) {
const result = [];
const n = arr.length;
for (let i = 0; i < n; i++) {
let isLeader = true;
for (let j = i + 1; j < n; j++) {
if (arr[j] > arr[i]) {
isLeader = false;
break;
}
}
if (isLeader) result.push(arr[i]);
}
return result;
}
console.log(leaders([1, 2, 3, 4, 0])); // Output: [4, 0]
Even though 0 is the smallest, it's the last element so there’s nothing after it, making it a leader by definition ✨
113
Complete this function to return the leaders in an array using the optimal approach
function leaders(arr) {
const result = [];
let maxRight = _______;
result.push(maxRight);
for (let i = _______; i >= 0; i--) {
if (________) {
maxRight = arr[i];
result.push(maxRight);
}
}
return result.reverse();
}
function leaders(arr) {
const result = [];
let maxRight = arr[arr.length - 1];
result.push(maxRight);
for (let i = arr.length - 2; i >= 0; i--) {
if (arr[i] >= maxRight) {
maxRight = arr[i];
result.push(maxRight);
}
}
return result.reverse();
}
114
Write code to check if the array is sorted in non-decreasing order using an iterative approach.
Array Example:
arr = [20, 23, 23, 45, 78, 88]
function arraySortedOrNot(arr, n) {
if (n === 0 || n === 1) return true;
for (let i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) return false;
}
return true;
}
let arr = [20, 23, 23, 45, 78, 88];
let n = arr.length;
if (arraySortedOrNot(arr, n)) {
console.log("Yes");
} else {
console.log("No");
}
115
Write code to check if the array is sorted in non-decreasing order using a recursive approach.
Array Example:
arr = [20, 23, 23, 45, 78, 88]
function arraySortedOrNot(a, n) {
if (n === 0 || n === 1) return true;
return a[n - 1] >= a[n - 2] && arraySortedOrNot(a, n - 1);
}
let arr = [20, 23, 23, 45, 78, 88];
let n = arr.length;
if (arraySortedOrNot(arr, n)) {
console.log("Yes");
} else {
console.log("No");
}
116
What is the definition of a sorted array in non-decreasing order?
A sorted array in non-decreasing order means that each element is greater than or equal to the previous one. In other words:
arr[i] >= arr[i-1] for every i (starting from the second element).
117
Explain the basic idea behind the iterative approach to check if an array is sorted in non-decreasing order.
In the iterative approach, you:
Start from the second element (index 1).
Compare it to the previous element (index i-1).
If any element is smaller than its previous element, the array is not sorted, and you return false.
If no such element is found, the array is sorted, and you return true.
118
How does the recursive approach to check if an array is sorted work?
In the recursive approach:
Base Case: If the array has only one element or none, it's considered sorted by definition.
You compare the last element (arr[n-1]) with the previous one (arr[n-2]).
If arr[n-1] >= arr[n-2], you recursively check the rest of the array.
If at any point arr[n-1] < arr[n-2], return false.
119
what is the time complexity of both the iterative and recursive methods for checking if an array is sorted?
Both methods have a time complexity of O(n), where n is the length of the array. This is because we need to check each element once to confirm whether it's sorted or not.
120
Why is an array of length 0 or 1 considered sorted, and how does this apply to both iterative and recursive approaches?
An array of length 0 or 1 is trivially sorted because there are no elements or just one element to compare.
Iterative approach: If the array length is 0 or 1, it directly returns true.
Recursive approach: The base case checks for length 0 or 1 and returns true.
121
Given the array [20, 20, 78, 98, 99, 100], is it sorted in non-decreasing order? Why?
Yes, the array is sorted.
Each element is greater than or equal to the previous one:
20 <= 20
20 <= 78
78 <= 98
98 <= 99
99 <= 100
122
Why does the recursive method for checking if an array is sorted have a higher space complexity than the iterative approach?
The recursive approach uses the call stack for each recursive call. Since the recursion depth is equal to the number of elements in the array (n), the space complexity is O(n).
In contrast, the iterative approach only uses a constant amount of space (O(1)).
123
How does the presence of duplicate elements affect whether an array is considered sorted?
Duplicates are allowed in a sorted array. As long as arr[i] >= arr[i-1] holds true, the array can still be sorted even if elements are equal. For example:
[20, 20, 78, 78] is sorted because the elements are in non-decreasing order.
124
Why is it important to check if an array is sorted in real-world applications?
Knowing whether an array is sorted can optimize algorithms:
Search algorithms: Binary search can only be applied efficiently to sorted arrays.
Optimization: Sorting can reduce the need for additional processing (like sorting the array repeatedly).
Data Integrity: In systems that rely on sorted data (e.g., databases), confirming the sorted order ensures data consistency.
125
You’re given a sorted array and need to remove duplicates in-place.
What key trick lets you do it in O(1) space?
Because the array is already sorted, all the duplicates are right next to each other.
So we can just compare each element to the previous one while going in a single pass—no need for extra data structures.
126
In the in-place removeDuplicates approach, what does the variable idx represent?
It marks the next index where a new unique element should be placed.
Basically, it builds the front part of the array with distinct values.
127
What’s the time complexity and space complexity of removing duplicates in-place from a sorted array, using the two-pointer method (aka no extra memory)?
⏱ Time: O(n) – loop runs once
💾 Space: O(1) – no extra storage, just a couple of variables
128
Fill in the blanks to complete the function:
js
Copy
Edit
function removeDuplicates(arr) {
if (arr.length === 0) return 0;
let idx = ___;
for (let i = 1; i < arr.length; i++) {
if (arr[i] !== arr[____]) {
arr[idx] = arr[i];
idx++;
}
}
return ___;
}
let idx = 1;
if (arr[i] !== arr[i - 1])
return idx;
129
Input: [1, 1, 2, 3, 3, 4, 5, 5]
After removeDuplicates, what’s in the first part of the array?
[1, 2, 3, 4, 5]
The rest of the array can be messy—irrelevant.
