Hi friends in this post we'll see some interesting questions on Arrays. In each question we'll try to solve the questions in possible number of ways, with different complexities and we'll discuss about the pros and cons.
If you guys have any alternate solutions please comment them, would be pleased to update the post.
Question 1. Reverse a given array.
i.e., if the given array is 1,3,2,4 the output expected is 4,2,3,1.
Solution(1): We can use two pointers say l (l for left), r (r for right). Here l runs from 0 to n/2 and r runs from n-1 to n/2. at every iteration we'll be swapping elements at position l with element at position r.
code snippet:
l=0;r=n-1;
while(l<r){
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
l++;r--;
}
space complexity: θ(n/2) implies θ(n).
Time Complexity: θ(1).
Solution(2):
This is a very simple example. We can do that by using a stack. Push all the elements in to the stack, then replace the existing elements into the array with the elements poped from that stack.
code snippet:
for(int i=0;i<n;i++){
stack.push(arr[i]);
}
for(int i=0;i<n;i++){
arr[i]=stack.pop();
}
time complexity: θ(n). No matter what we need to iterate all the elements.
space complexity: θ(n). We need a stack of size n.
Solution(3): using single position variable:
Using just one position variable we could accomplish the task, with simple logic. Just we need to swap elements in this fashion.
0 with n-1,
1 with n-2,
2 with n-3,---> n-2-1.
.
.
i with n-i-1
with a condition that, we should terminate the moment when i<n/2. i.e., we should stop once we reach the middle of the array, or else there is a risk of re-swapping.
code snippet:
while(i<n/2){
swap(a[i],arr[n-i-1]);
}
return arr;
time complexity: θ(n).
space complexity: θ(1).
Question 2. Given an array with number of zeros and non-zero elements. Move all the zeros to the last of the array, and non-zeros to to the start of the array.
i.e., Let the given array be 2,0,3,0,4,0,0,1,2 be modified to 2,3,4,1,2,0,0,0,0 i.e., pushing all the zeros to right corner.
Solution(1):
Simple, Sort the array in descending order. Since the order of the remaining elements doesn't matter.
Solution(2):
A simple solution for this is to sort and reverse the array.
Sorting takes O(n log n).
reversing an array takes θ(n) complexity.
Thus overall complexity O(n log n).
Solution(3):
Lets maintain two variables 'left' and 'right', similar to the solution 1 of First question. keep increasing left by 1 same time decrease right by 1 as long as left is less than right (while(left<right)), swap the elements at the locations left and right if element at left is 0. decrease right by 1 if element at right is 0, since we should not swap 0 to left location as risk of 0 remaining on left side is there.
code snippet:
left=0;right=n-1;
while(left<right){
if(arr[right]==0)right--;
if(left<right && arr[right]==0)
swap(arr[left],arr[right]);
left++;right--;
}
Complexities:
Time complexity: O(n)
Question 3. given an array of integer elements, and an element k. Find pair of elements in the given array such that there sum is equal to k.
Solution 1: for every element match with every other element to find weather it satisfies the given condition.
code snippet:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(i!=j && (arr[i]+arr[j])==k)
printf("%d,%d",i,j);
i!=j is check to see if we are not matching element to itself.
complexity: O(n2)
Solution 2:
Since O(n2) is not that appreciable we would try better than that. First we would sort the array, this will take a complexity of O(n log n) at most. Then we'll take each element say 'e' and the corresponding element which will pair with it to produce 'k' on adding is 'k-e'. Thus our aim is to iterate a search logic for each element of the set. Since we specified for each element we need 'n' iterations and since in each iteration we are searching we need at most 'log n' - binary search (that's why we sorted the array, for binary search). Thus searching for each element we end up with O(n log n).
1st O(n log n) for sorting and 2nd O(n log n) for running search n times.
Thus 2xO(n log n) which basically is O(n log n)
code snippet:
QuickSort(arr); //----------------------> Sorting would be handled in sorting post.
scanf("%d",&k);
int KminE; // k-e
for(int i=0;i<n;i++){ // --------------> iterating n times
KminE=k-arr[i];
search(arr,KminE); // --------------> searching takes log n iterations
}
Time Complexity: O(n log n).
Solution 3: There is one more cool solution. We could accomplish the task in O(n) complexity. But with a drawback of using extra memory of O(n). Here goes the solution.
Using HashSet --------------> (Always remember, if we are allowed to use an extra memory and search for an element is our main task, go for HashSet it helps a lot.)
First read all the elements from the array and place it in HashSet. It takes n iterations.
Now check if k-e exists in HashSet for each element 'e' in the array.
Code Snippet: ----> (please don't mind I'm not concentrating on any language, I am just giving you the code glims. Now I am going to use java notations).
HashSet hs=new HashSet(n);
for(int i=0;i<n;i++)
hs.add(arr[i]);
for(int i=0;i<n;i++)
if(hs.contains(k-arr[i])) System.out.println("x = "+arr[i]+" y = "+ k-arr[i]);
Time Complexity: O(n)
Space Complexity : O(n).
note: Here we need to assume that the values given are unique. Since Set hold only unique values, we might end-up in confusion weather e and k-e are one and the same, or not. i.e., if the given k is 8. And if 4,4 are the pair of results. There might be 2 4's in the array, or we might have picked 4 and itself from the HashSet, since HashSet contains only one 4, no matter how many 4's we have inserted. We'll discuss this in case you guys have need any clarification.
Question 4: Given an array on 'n' elements of 0s and 1s. Sort the array.
Solution(1):
Sort the array using standard O(n log n) logic.
Time Complexity: O(n log n)
Solution(2):
Using right and left position variables, similar to solution 1 of problem 1. Swap elements of left and right, if element at left is 1 and right is 0.
Time Complexity: O(n)
Question 5: Given an array of 'n' elements. Each element in the array has a duplicate except one. For eg.
The given array is: 5,3,6,5,7,6,3,7,7. Here the element to be found is 7 since doesn't have pair. Simple way to say find the number which is present odd number of times in the array.
Solution(1): Sort the array, cancel out adjacent elements if they are equal, if we can't find an equal number to cancel return that number.
In the above example on sorting we have the series as: 3,3,5,5,6,6,7,7,7. 3 cancels its adjacent 3, so does 5 till 7 cancels 7 leaving the last seven with no element to pair. So we return 7.
code snippet:
QuickSort(arr);
for(int i=0;i<n-1;i=i+2){ // taking alternate elements
if(i==n-1)return arr[i]; // if the element to return is the last element in the array.
if(arr[i]!=arr[i+1)) return arr[i];
}
Time Complexity: O(n log n) -------> for sorting.
Solution 2: Using HashSet. Add element from given array, if it is not present in the HashSet. If present remove that element.
code snippet:
HashSet hs=new HashSet();
for(int i=0;i<n;i++){
if(hs.contains(arr[i]))
hs.remove(arr[i]);
else
hs.add(arr[i]);
}
if(!hs.empty())
{
Iterator it=hs.iterator();
return it.next();
}
return -1;
Time Complexity : θ(n)
Space Complexity: O(n)
Solution 3: Here is a beautiful technique. Remember bit-wise operator called XOR. Any how we'll have a short introduction about it.
XOR works as follows:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
An interesting behavior of this operator is: an element say some 'a' on XORing with itself leaves 0 as result.
Also a XOR b XOR a = b.
Thus if we simplly XOR all the elements of the given array. The result is the element which lacks its corresponding pair.
code snippet:
int retVal;
for(int i=0;i<n;i++)
{
retVal=retVal ^ arr[i];
}
return retVal;
Time Complexity: θ(n)
Question 6: Given an array of integers (both positive and negative). Among all the possible sub-arrays find the sub-array with maximum sum.
Example: If the given input is 5, -6, 5, -6, 7, -3. Here the sub-string with maximum sum is a single element and i.e., 7.
In this problem we can do that using 2 variables, 'max' and 'localmax'.
max - the value returnable.
localmax - the value we frequently compute and compare with max. If max is found to be less than localmax we'll replace max value with localmax.
code snippet:
max=localmax=0;
for(int i=0;i<n;i++){
localmax=maximum_of(localmax+arr[i],arr[i]);
max=maximum_of(localmax,max);
}
return max;
maximum_of(int i,int j){
if(i>j)return i;
else return j;
}
If you guys have any alternate solutions please comment them, would be pleased to update the post.
Question 1. Reverse a given array.
i.e., if the given array is 1,3,2,4 the output expected is 4,2,3,1.
Solution(1): We can use two pointers say l (l for left), r (r for right). Here l runs from 0 to n/2 and r runs from n-1 to n/2. at every iteration we'll be swapping elements at position l with element at position r.
code snippet:
l=0;r=n-1;
while(l<r){
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
l++;r--;
}
space complexity: θ(n/2) implies θ(n).
Time Complexity: θ(1).
Solution(2):
This is a very simple example. We can do that by using a stack. Push all the elements in to the stack, then replace the existing elements into the array with the elements poped from that stack.
code snippet:
for(int i=0;i<n;i++){
stack.push(arr[i]);
}
for(int i=0;i<n;i++){
arr[i]=stack.pop();
}
time complexity: θ(n). No matter what we need to iterate all the elements.
space complexity: θ(n). We need a stack of size n.
Solution(3): using single position variable:
Using just one position variable we could accomplish the task, with simple logic. Just we need to swap elements in this fashion.
0 with n-1,
1 with n-2,
2 with n-3,---> n-2-1.
.
.
i with n-i-1
with a condition that, we should terminate the moment when i<n/2. i.e., we should stop once we reach the middle of the array, or else there is a risk of re-swapping.
code snippet:
while(i<n/2){
swap(a[i],arr[n-i-1]);
}
return arr;
time complexity: θ(n).
space complexity: θ(1).
Question 2. Given an array with number of zeros and non-zero elements. Move all the zeros to the last of the array, and non-zeros to to the start of the array.
i.e., Let the given array be 2,0,3,0,4,0,0,1,2 be modified to 2,3,4,1,2,0,0,0,0 i.e., pushing all the zeros to right corner.
Solution(1):
Simple, Sort the array in descending order. Since the order of the remaining elements doesn't matter.
Solution(2):
A simple solution for this is to sort and reverse the array.
Sorting takes O(n log n).
reversing an array takes θ(n) complexity.
Thus overall complexity O(n log n).
Solution(3):
Lets maintain two variables 'left' and 'right', similar to the solution 1 of First question. keep increasing left by 1 same time decrease right by 1 as long as left is less than right (while(left<right)), swap the elements at the locations left and right if element at left is 0. decrease right by 1 if element at right is 0, since we should not swap 0 to left location as risk of 0 remaining on left side is there.
code snippet:
left=0;right=n-1;
while(left<right){
if(arr[right]==0)right--;
if(left<right && arr[right]==0)
swap(arr[left],arr[right]);
left++;right--;
}
Complexities:
Time complexity: O(n)
Question 3. given an array of integer elements, and an element k. Find pair of elements in the given array such that there sum is equal to k.
Solution 1: for every element match with every other element to find weather it satisfies the given condition.
code snippet:
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(i!=j && (arr[i]+arr[j])==k)
printf("%d,%d",i,j);
i!=j is check to see if we are not matching element to itself.
complexity: O(n2)
Solution 2:
Since O(n2) is not that appreciable we would try better than that. First we would sort the array, this will take a complexity of O(n log n) at most. Then we'll take each element say 'e' and the corresponding element which will pair with it to produce 'k' on adding is 'k-e'. Thus our aim is to iterate a search logic for each element of the set. Since we specified for each element we need 'n' iterations and since in each iteration we are searching we need at most 'log n' - binary search (that's why we sorted the array, for binary search). Thus searching for each element we end up with O(n log n).
1st O(n log n) for sorting and 2nd O(n log n) for running search n times.
Thus 2xO(n log n) which basically is O(n log n)
code snippet:
QuickSort(arr); //----------------------> Sorting would be handled in sorting post.
scanf("%d",&k);
int KminE; // k-e
for(int i=0;i<n;i++){ // --------------> iterating n times
KminE=k-arr[i];
search(arr,KminE); // --------------> searching takes log n iterations
}
Time Complexity: O(n log n).
Solution 3: There is one more cool solution. We could accomplish the task in O(n) complexity. But with a drawback of using extra memory of O(n). Here goes the solution.
Using HashSet --------------> (Always remember, if we are allowed to use an extra memory and search for an element is our main task, go for HashSet it helps a lot.)
First read all the elements from the array and place it in HashSet. It takes n iterations.
Now check if k-e exists in HashSet for each element 'e' in the array.
Code Snippet: ----> (please don't mind I'm not concentrating on any language, I am just giving you the code glims. Now I am going to use java notations).
HashSet hs=new HashSet(n);
for(int i=0;i<n;i++)
hs.add(arr[i]);
for(int i=0;i<n;i++)
if(hs.contains(k-arr[i])) System.out.println("x = "+arr[i]+" y = "+ k-arr[i]);
Time Complexity: O(n)
Space Complexity : O(n).
note: Here we need to assume that the values given are unique. Since Set hold only unique values, we might end-up in confusion weather e and k-e are one and the same, or not. i.e., if the given k is 8. And if 4,4 are the pair of results. There might be 2 4's in the array, or we might have picked 4 and itself from the HashSet, since HashSet contains only one 4, no matter how many 4's we have inserted. We'll discuss this in case you guys have need any clarification.
Question 4: Given an array on 'n' elements of 0s and 1s. Sort the array.
Solution(1):
Sort the array using standard O(n log n) logic.
Time Complexity: O(n log n)
Solution(2):
Using right and left position variables, similar to solution 1 of problem 1. Swap elements of left and right, if element at left is 1 and right is 0.
Time Complexity: O(n)
Question 5: Given an array of 'n' elements. Each element in the array has a duplicate except one. For eg.
The given array is: 5,3,6,5,7,6,3,7,7. Here the element to be found is 7 since doesn't have pair. Simple way to say find the number which is present odd number of times in the array.
Solution(1): Sort the array, cancel out adjacent elements if they are equal, if we can't find an equal number to cancel return that number.
In the above example on sorting we have the series as: 3,3,5,5,6,6,7,7,7. 3 cancels its adjacent 3, so does 5 till 7 cancels 7 leaving the last seven with no element to pair. So we return 7.
code snippet:
QuickSort(arr);
for(int i=0;i<n-1;i=i+2){ // taking alternate elements
if(i==n-1)return arr[i]; // if the element to return is the last element in the array.
if(arr[i]!=arr[i+1)) return arr[i];
}
Time Complexity: O(n log n) -------> for sorting.
Solution 2: Using HashSet. Add element from given array, if it is not present in the HashSet. If present remove that element.
code snippet:
HashSet hs=new HashSet();
for(int i=0;i<n;i++){
if(hs.contains(arr[i]))
hs.remove(arr[i]);
else
hs.add(arr[i]);
}
if(!hs.empty())
{
Iterator it=hs.iterator();
return it.next();
}
return -1;
Time Complexity : θ(n)
Space Complexity: O(n)
Solution 3: Here is a beautiful technique. Remember bit-wise operator called XOR. Any how we'll have a short introduction about it.
XOR works as follows:
0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
An interesting behavior of this operator is: an element say some 'a' on XORing with itself leaves 0 as result.
Also a XOR b XOR a = b.
Thus if we simplly XOR all the elements of the given array. The result is the element which lacks its corresponding pair.
code snippet:
int retVal;
for(int i=0;i<n;i++)
{
retVal=retVal ^ arr[i];
}
return retVal;
Time Complexity: θ(n)
Question 6: Given an array of integers (both positive and negative). Among all the possible sub-arrays find the sub-array with maximum sum.
Example: If the given input is 5, -6, 5, -6, 7, -3. Here the sub-string with maximum sum is a single element and i.e., 7.
In this problem we can do that using 2 variables, 'max' and 'localmax'.
max - the value returnable.
localmax - the value we frequently compute and compare with max. If max is found to be less than localmax we'll replace max value with localmax.
code snippet:
max=localmax=0;
for(int i=0;i<n;i++){
localmax=maximum_of(localmax+arr[i],arr[i]);
max=maximum_of(localmax,max);
}
return max;
maximum_of(int i,int j){
if(i>j)return i;
else return j;
}
No comments:
Post a Comment