Arrays in One shot | Revision - 4 | C++ and DSA Foundation Course

Key Concepts

• Arrays: Data structures that store a collection of elements of the same type in contiguous memory locations.
• Sorted Arrays: Arrays where elements are arranged in a specific order (e.g., increasing or decreasing).
• Two-Pointer Technique: An algorithmic technique that uses two pointers to traverse a data structure (usually an array) to find a solution efficiently.
• Time Complexity: A measure of how the execution time of an algorithm grows as the input size increases.
• Space Complexity: A measure of the amount of memory space required by an algorithm.
• Absolute Difference: The non-negative difference between two numbers, regardless of their order.
• Unique Pairs: Pairs of elements that satisfy a specific condition (e.g., sum or difference) and are distinct from each other based on certain criteria (e.g., index or value).

Problem 1: Merging Two Sorted Arrays

Main Topic: Merging two sorted arrays into a single sorted array.

Key Points:

• Given two sorted arrays, ARR1 of size M and ARR2 of size N, both sorted in increasing order.
• The goal is to merge them into a single sorted array of size M + N.
• The final array must also be sorted in increasing order.
• The algorithm uses two pointers, i and j, to iterate through ARR1 and ARR2, respectively.
• It compares the elements at ARR1[i] and ARR2[j] and adds the smaller element to the result array.
• The corresponding pointer is then incremented.
• If one array is exhausted before the other, the remaining elements of the other array are added to the result array.

Step-by-Step Process:

1. Initialize pointers i = 0, j = 0, and k = 0 (index for the result array).
2. Create a result array result of size M + N.
3. While i < M and j < N:
   • If ARR1[i] <= ARR2[j]:
     • result[k] = ARR1[i]
     • i++
   • Else:
     • result[k] = ARR2[j]
     • j++
   • k++
4. If i < M:
   • While i < M:
     • result[k] = ARR1[i]
     • i++
     • k++
5. If j < N:
   • While j < N:
     • result[k] = ARR2[j]
     • j++
     • k++
6. Return the result array.

Example:

• ARR1 = [1, 6, 7, 10, 11]
• ARR2 = [0, 1, 3, 8, 12, 15, 18]
• Result = [0, 1, 1, 3, 6, 7, 8, 10, 11, 12, 15, 18]

Code Implementation:

The code implements the above algorithm using a while loop and if-else conditions to compare elements and merge the arrays.

Key Takeaways:

• The two-pointer technique is efficient for merging sorted arrays.
• The algorithm has a time complexity of O(M + N), where M and N are the sizes of the input arrays.

Problem 2: Finding a Pair with a Given Sum

Main Topic: Finding if a pair exists in a sorted array with a sum equal to a given value.

Key Points:

• Given a sorted array ARR and a target sum X.
• The goal is to determine if there exists a pair of elements in ARR such that their sum is equal to X.
• The algorithm uses two pointers, i and j, initialized to the start and end of the array, respectively.
• It calculates the sum of the elements at ARR[i] and ARR[j].
• If the sum is equal to X, it returns true.
• If the sum is less than X, it increments i to increase the sum.
• If the sum is greater than X, it decrements j to decrease the sum.
• If the pointers cross each other (i >= j), it returns false.

Step-by-Step Process:

1. Initialize pointers i = 0 and j = N - 1, where N is the size of the array.
2. Initialize a boolean variable found = false.
3. While i < j:
   • Calculate sum = ARR[i] + ARR[j].
   • If sum == X:
     • found = true
     • Break the loop.
   • Else if sum < X:
     • i++
   • Else:
     • j--
4. Return found.

Example:

• ARR = [-2, -1, 0, 3, 6, 8, 11, 12]
• X = 7
• Result = true (because -1 + 8 = 7)

Code Implementation:

The code implements the above algorithm using a while loop and if-else conditions to adjust the pointers based on the sum.

Key Takeaways:

• The two-pointer technique is efficient for finding pairs with a given sum in a sorted array.
• The algorithm has a time complexity of O(N), where N is the size of the array.

Problem 3: Finding a Pair with a Given Absolute Difference

Main Topic: Finding if a pair exists in a sorted array with an absolute difference equal to a given value.

Key Points:

• Given a sorted array ARR and a target absolute difference X.
• The goal is to determine if there exists a pair of elements in ARR such that their absolute difference is equal to X.
• The algorithm uses two pointers, i and j, initialized to the start of the array.
• It calculates the absolute difference between the elements at ARR[i] and ARR[j].
• If the absolute difference is equal to X, it returns true.
• If the absolute difference is less than X, it increments j to increase the absolute difference.
• If the absolute difference is greater than X, it increments i to decrease the absolute difference.
• The loop continues until j reaches the end of the array.

Step-by-Step Process:

1. Initialize pointers i = 0 and j = 0.
2. Initialize a boolean variable found = false.
3. While j < N:
   • Calculate absoluteDifference = abs(ARR[i] - ARR[j]).
   • If absoluteDifference == X:
     • found = true
     • Break the loop.
   • Else if absoluteDifference < X:
     • j++
   • Else:
     • i++
     • If i == j:
       • j++
4. Return found.

Example:

• ARR = [1, 6, 8, 12]
• X = 7
• Result = true (because |1 - 8| = 7)

Code Implementation:

The code implements the above algorithm using a while loop and if-else conditions to adjust the pointers based on the absolute difference.

Key Takeaways:

• The two-pointer technique can be adapted to find pairs with a given absolute difference in a sorted array.
• The algorithm has a time complexity of O(N), where N is the size of the array.

Problem 4: Squaring Elements of a Sorted Array

Main Topic: Squaring the elements of a sorted array and returning a new sorted array.

Key Points:

• Given a sorted array ARR (can contain negative and positive numbers).
• The goal is to return a new array containing the squares of the elements of ARR, sorted in increasing order.
• The algorithm uses two pointers, i and j, initialized to the start and end of the array, respectively.
• It compares the absolute values of the elements at ARR[i] and ARR[j].
• The element with the larger absolute value is squared and added to the result array at the end.
• The corresponding pointer is then moved towards the center of the array.
• The process continues until i and j cross each other.

Step-by-Step Process:

1. Initialize pointers i = 0 and j = N - 1, where N is the size of the array.
2. Create a result array result of size N.
3. Initialize k = N - 1 (index for the result array).
4. While i <= j:
   • If abs(ARR[i]) > abs(ARR[j]):
     • result[k] = ARR[i] * ARR[i]
     • i++
   • Else:
     • result[k] = ARR[j] * ARR[j]
     • j--
   • k--
5. Return the result array.

Example:

• ARR = [-5, -4, -3, -2, -1]
• Result = [1, 4, 9, 16, 25]

Code Implementation:

The code implements the above algorithm using a while loop and if-else conditions to compare absolute values and populate the result array.

Key Takeaways:

• The two-pointer technique is effective for squaring and sorting elements in a sorted array, especially when negative numbers are involved.
• The algorithm has a time complexity of O(N), where N is the size of the array.

Problem 5: Counting Unique Pairs with a Given Sum

Main Topic: Counting the number of unique pairs in a sorted array with a sum equal to a given value.

Key Points:

• Given a sorted array ARR and a target sum X.
• The goal is to count the number of unique pairs of elements in ARR such that their sum is equal to X.
• The algorithm uses two pointers, i and j, initialized to the start and end of the array, respectively.
• It calculates the sum of the elements at ARR[i] and ARR[j].
• If the sum is equal to X, it increments the count and moves both pointers towards the center.
• If the sum is less than X, it increments i to increase the sum.
• If the sum is greater than X, it decrements j to decrease the sum.
• The loop continues until i and j cross each other.

Step-by-Step Process:

1. Initialize pointers i = 0 and j = N - 1, where N is the size of the array.
2. Initialize a counter variable count = 0.
3. While i < j:
   • Calculate sum = ARR[i] + ARR[j].
   • If sum == X:
     • count++
     • i++
     • j--
   • Else if sum < X:
     • i++
   • Else:
     • j--
4. Return count.

Example:

• ARR = [1, 3, 4, 6]
• X = 7
• Result = 2 (because 1 + 6 = 7 and 3 + 4 = 7)

Code Implementation:

The code implements the above algorithm using a while loop and if-else conditions to adjust the pointers based on the sum and increment the count.

Key Takeaways:

• The two-pointer technique can be used to count unique pairs with a given sum in a sorted array.
• The algorithm has a time complexity of O(N), where N is the size of the array.

Synthesis/Conclusion

The video effectively demonstrates the application of the two-pointer technique to solve various array-based problems. The problems range from merging sorted arrays to finding pairs with specific properties (sum or difference) and manipulating array elements (squaring). The two-pointer technique proves to be an efficient approach for solving these problems, especially when the input array is sorted. The video provides clear explanations, step-by-step processes, and code implementations for each problem, making it a valuable resource for learning and practicing array problem-solving techniques. The emphasis on understanding the problem constraints and choosing the appropriate pointer movements is crucial for developing efficient and correct solutions.