General Questions Flashcards
If you see shorted path, what should you think of ?
BFS
What are the time complexity & Auxiliary Space of the Two Pointers Technique
Time Complexity: O(n log n) (As sort function is used)
Auxiliary Space: O(1), since no extra space has been taken.
What is the Naïve Approach ?
A naive approach is the simplest and most straightforward way to solve a problem.
It is often the first solution that comes to mind, and it may be the most efficient solution in some cases. However, naive approaches can often be inefficient or ineffective, especially for complex problems.
What are two examples of Naive Approach ?
Linear search: This is the simplest way to search for an element in an array. It starts at the beginning of the array and compares the target element to each element in the array until it finds a match or reaches the end of the array.
Brute-force string matching: This is the simplest way to match a pattern in a string. It compares the pattern character by character to the string, starting at the beginning of the string. If a mismatch is found, the pattern is moved to the next position in the string and the comparison is repeated.
What s the Two Pointers Technique
We take two pointers, one representing the first element and other representing the last element of the array, and then we add the values kept at both the pointers. If their sum is smaller than X then we shift the left pointer to right or if their sum is greater than X then we shift the right pointer to left, in order to get closer to the sum. We keep moving the pointers until we get the sum as X.
What’s the code of the two pointer technique
import java.util.Arrays;
import java.util.List;
public class PairSum {
// Two pointer technique based solution to find
// if there is a pair in A[0..N-1] with a given sum.
public static int isPairSum(List<Integer> A, int N,
int X)
{
// represents first pointer
int i = 0;</Integer>
// represents second pointer
int j = N - 1;
while (i < j) {
// If we find a pair
if (A.get(i) + A.get(j) == X)
return 1;
// If sum of elements at current
// pointers is less, we move towards
// higher values by doing i++
else if (A.get(i) + A.get(j) < X)
i++;
// If sum of elements at current
// pointers is more, we move towards
// lower values by doing j--
else
j--;
}
return 0;
}
// Driver code
public static void main(String[] args)
{
// array declaration
List<Integer> arr
= Arrays.asList(2, 3, 5, 8, 9, 10, 11);
// value to search
int val = 17;
// size of the array
int arrSize = arr.size();
// array should be sorted before using the
// two-pointer technique
arr.sort(null);
// Function call
System.out.println(isPairSum(arr, arrSize, val)
!= 0);
} } https://www.geeksforgeeks.org/two-pointers-technique/
Given an array of sorted numbers, remove all duplicate number instances from it in-place, such that each element appears only once. The relative order of the elements should be kept the same and you should not use any extra space so that the solution has a space complexity of .
Move all the unique elements at the beginning of the array and after moving return the length of the subarray that has no duplicate in it.
Example 1:
Input: [2, 3, 3, 3, 6, 9, 9]
Output: 4
Explanation: The first four elements after removing the duplicates will be [2, 3, 6, 9].
public static int remove(int[] arr) {
int nextNonDuplicate = 1; // index of the next non-duplicate element
for (int i = 0; i < arr.length; i++) {
if (arr[nextNonDuplicate - 1] != arr[i]) {
arr[nextNonDuplicate] = arr[i];
nextNonDuplicate++;
}
}
return nextNonDuplicate; }
Remove element from array:
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
Return k.
Example 1:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,,]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).
class Solution {
public int removeElement(int[] nums, int val) {
int next =0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=val){
nums[next]=nums[i];
next++;
}
}
return next;
}
}
Squaring a sorted array
Given a sorted array, create a new array containing squares of all the numbers of the input array in the sorted order.
Example 1:
Input: [-2, -1, 0, 2, 3]
Output: [0, 1, 4, 4, 9]
class Solution {
public static int[] makeSquares(int[] arr) {
int n = arr.length;
int[] squares = new int[n];
// TODO: Write your code here
int i=0,j=n-1;
int lastIndex=n-1;
while(i<j){
if((arr[j]arr[j])>=(arr[i]arr[i])){
squares[lastIndex]=arr[j]arr[j];
j–;
}else if(arr[i]arr[i]>arr[j]arr[j]){
squares[lastIndex]=arr[i]arr[i];
i++;
}
lastIndex–;
}
return squares;
}
}
Triplet Sum to Zero
Given an array of unsorted numbers, find all unique triplets in it that add up to zero.
Example 1:
Input: [-3, 0, 1, 2, -1, 1, -2]
Output: [[-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Explanation: There are four unique triplets whose sum is equal to zero. smallest sum.’
Example 2:
Input: [-5, 2, -1, -2, 3]
Output: [[-5, 2, 3], [-2, -1, 3]]
Explanation: There are two unique triplets whose sum is equal to zero.
import java.util.*;
class Solution {
public static List<List<Integer>> searchTriplets(int[] arr) {
Arrays.sort(arr);
List<List<Integer>> triplets = new ArrayList<>();
for (int i = 0; i < arr.length - 2; i++) {
if (i > 0 && arr[i] == arr[i - 1]) // skip same element to avoid duplicate triplets
continue;
searchPair(arr, -arr[i], i + 1, triplets);
}</Integer></Integer>
return triplets; }
private static void searchPair(int[] arr, int targetSum,
int left, List<List<Integer>> triplets) {
int right = arr.length - 1;
while (left < right) {
int currentSum = arr[left] + arr[right];
if (currentSum == targetSum) { // found the triplet
triplets.add(Arrays.asList(-targetSum, arr[left], arr[right]));
left++;
right--;
while (left < right && arr[left] == arr[left - 1])
left++; // skip same element to avoid duplicate triplets
while (left < right && arr[right] == arr[right + 1])
right--; // skip same element to avoid duplicate triplets
} else if (targetSum > currentSum)
left++; // we need a pair with a bigger sum
else
right--; // we need a pair with a smaller sum
}
}</Integer>
public static void main(String[] args) {
System.out.println(Solution.searchTriplets(
new int[] { -3, 0, 1, 2, -1, 1, -2 }));
System.out.println(Solution.searchTriplets(new int[] { -5, 2, -1, -2, 3 }));
}
}
