CA 04 - Two Sum & Sorted Two Sum

TWO SUM PROBLEM

I solved the Two Sum problem from LeetCode in java using brute force method. The problem gives an array of integers and a target value. I need to find two indices so that the numbers at those indices add to the target. and i can't use the same element twice, and there will always be one valid answer.

To solve this, I used a simple method. I took one number from the array and compared it with every number that comes after it. For every pair i checked if their sum is equal to the target. If it is i need to return the indices of those two numbers.

I used two loops for this. The first loop picks one number, and the second loop checks the remaining numbers. As soon as it find a pair that matches the target, it return the answer.

This method works correctly but takes more time because it checks all pairs. The time complexity is O(n^2). The space complexity is O(1) because no extra space is used.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[i] + nums[j] == target) {
                    return new int[] {i, j};
                }
            }
        }
        return new int[] {};
    }
}

SORTED TWO SUM

The task is to find two numbers such that their sum equals the target and return their positions. I also need to add 1 to the indices before returning them.

To solve this, i used a simple brute force method. It checked every possible pair of numbers in the array and saw if their sum equals the target.

I used two loops for this. The first loop picks one number, and the second loop checks all the numbers after it. For each pair, It added the two numbers and compared the result with the target. If the sum matches, it return the indices. return i + 1 and j + 1.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for(int i = 0; i < numbers.length; i++) {
            for(int j = i + 1; j < numbers.length; j++) {
                if(numbers[i] + numbers[j] == target) {
                    return new int[] {i + 1, j + 1};
                }
            }
        }
        return new int[] {};
    }
}

This method works correctly but it takes more time. The time complexity is O(n^2) because of the nested loops. The space complexity is O(1) since no extra space is used.