C# Coding Test Course, Two Pointers

Problem Description

Given an integer array nums and an integer target,
solve the problem of finding the indices of two numbers in the nums array that add up to equal target and return those indices.
Users can assume that there is exactly one pair of integers that exists.

Input Example

• nums = [2, 7, 11, 15]
• target = 9

Output Example

[0, 1]

Algorithm Approach

To solve this problem, we will approach it by using the two-pointer technique to traverse the array while
comparing the sum of the values pointed to by the two pointers to find the desired value.
The two-pointer technique is typically applied to sorted arrays, but in this problem, the two pointers
can point to the same array while considering various cases.

Problem Solving Process

1. Set initial indices for the two pointers in the array

Initialize the starting pointer left to 0 and the ending pointer right to the length of the array – 1.
This allows us to explore the array through nums[left] and nums[right].

2. Move pointers in a loop

For example, use the following loop to compare the sum of the values pointed to by the two pointers:

while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    return new int[] { left, right };
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }

3. Return the result

Once we find valid indices for left and right, we return those values.
If no valid values are found, handle it by returning null or throwing an exception.

C# Code Implementation

using System;

class Program {
    static void Main(string[] args) {
        int[] nums = { 2, 7, 11, 15 };
        int target = 9;
        int[] result = TwoSum(nums, target);
        Console.WriteLine($"[{result[0]}, {result[1]}]");
    }

    static int[] TwoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.Length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[] { left, right };
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        // If no matching pair is found
        throw new Exception("No two sum solution");
    }
}
            

Solution Analysis

1. Time Complexity

The time complexity of this algorithm is O(n).
Since the left and right pointers scan the array once, performance remains O(n) even in the worst case.

2. Space Complexity

The space complexity is O(1). There is no use of additional arrays or lists, making it space-efficient.

Conclusion

In this course, we solved a simple problem using the two-pointer algorithm.
The two-pointer technique can be utilized effectively in many problems and is a useful method for
traversing arrays or lists. It would be beneficial to further study this technique with a variety of examples.