Leetcode Problem 1: Two Sum

As I work my way through LeetCode problems, I’ll document my solutions with an explanation, both for myself to remember what I did, and for the readers who might not be satisfied with the official approach. I’ve found that the official solutions, although fast, and memory efficient, are not always intuitive to me.

With that preamble aside, here are my Python and C++ solutions.

Python solution Link to heading

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        i = 0

        while i + 1 < n:
            sentinel = nums[i]
            j = i + 1
            while j < n:
                if sentinel + nums[j] == target:
                    return [i, j]
                j += 1

            i += 1

C++ solution Link to heading

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size(), i = 0;
        vector<int> sol;

        while (i + 1 < n) {
            int sentinel = nums[i];
            for (int j = i + 1; j < n; j++) {
                if (sentinel + nums[j] == target) {
                    return {i, j};
                }
            }
            i++;
        }
        return sol;
    }
};

This exercise is quite straightforward. To solve it, all we need to do is iterate through each element of nums by keeping one element constant (the sentinel) until we find the target. The process is simplified thanks to the constraint:

  • only one valid answer exists.

That ensures than we target is reached, it’s the only valid solution.

Python statistics Link to heading

Runtime: 40 ms         -> faster than 94.48% of Python 3 submissions.
Memory Usage: 14.5 MB

C++ statistics Link to heading

Runtime: 4 ms         -> faster than 94.86% of C++ online submissions for Two Sum.
Memory Usage: 8.9 MB  -> less than 81.43% of C++ online submissions for Two Sum.

Complexity analysis Link to heading

  • Time complexity: O(n2) because in the worst-case scenario, for each element, we end up fully looping through the array — at a cost of O(n) — twice in nested fashion in order to find the other number that summed with the current one is equal to the target.

  • Space complexity: O(1) because the input array is not modified, and the solution array is always of size 2, regardless of input size.



Share on:
LinkedIn