LeetCode Decoded:

Solving “Add Two Numbers” and “Two Sum” with Ease

In this article, I will guide you through two popular LeetCode challenges: “Add Two Numbers” and “Two Sum.” We’ll explore how to approach these problems, understand the underlying concepts, and implement effective solutions. These challenges are excellent for honing your problem-solving skills and gaining confidence in handling linked lists and arrays.

Q1) Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

The solution I explored there,

public class Solution {
    public int[] TwoSum(int[] nums, int target) 
    {
        int firstCounter = 0;
        int secondCounter = 1;

        while(firstCounter < nums.Length)
        {
            if(secondCounter < nums.Length)
            {

                if (nums[firstCounter] + nums[secondCounter] == target)
                    break;

                    secondCounter++;
            }else
            {
                    firstCounter++;
                    secondCounter=firstCounter+1;
            }
                
        }

            return new int[] {firstCounter, secondCounter};
    }

}

The provided solution is a brute-force approach where we use two counters to iterate through the array and find the indices of the two numbers that sum up to the target.

However, it’s important to note that this solution has a time complexity of O(n²) due to the nested loop structure, which may not be optimal for large inputs. More efficient solutions, such as using a hash map to store previously encountered elements, can reduce the time complexity to O(n).

Q2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

The solution I explored there,

public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {


        ListNode head = new ListNode(-1);
        ListNode tempNode = head;
        int rem = 0;
        int sum = 0;

        while(l1 != null || l2!=null || rem >0){
            int l1Val=0;
            int l2Val=0;
                
            if(l1 != null){
                l1Val =l1.val;
                l1 =l1.next;
            }
            if(l2 != null){
               l2Val =l2.val;
                l2 =l2.next; 
            }

            sum = l1Val + l2Val +rem;
            int nodeVal = sum % 10;
            rem = sum/10;

            tempNode.next = new ListNode(nodeVal);
            tempNode = tempNode.next;
        }
        return head.next;
    }
}

The Add Two Numbers problem is a common algorithmic challenge that involves adding two non-negative integers represented as linked lists. The digits are stored in reverse order, and each node contains a single digit. The goal is to add the two numbers and return the sum as a linked list. We can assume that the input lists do not contain any leading zeros, except for the number 0 itself.

In here,

ListNode head = new ListNode(-1);
ListNode tempNode = head;

• Purpose: head is a dummy node.
• Why it’s used: It simplifies list operations by providing a starting point. Without it, handling edge cases like an empty input list or the initial node creation would be more complex.

— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —

• Purpose: tempNode is used to traverse and build the new linked list.
• Why it’s used: As you create new nodes for the sum of l1 and l2, tempNode helps to link these nodes together.

while(l1 != null || l2 != null || rem > 0){
    ...
    tempNode.next = new ListNode(nodeVal);
    tempNode = tempNode.next;
}

• In each iteration, a new node (new ListNode(nodeVal)) is created with the value nodeVal.
• tempNode.next is set to point to this new node, effectively appending it to the list.
• tempNode is then moved to point to this new node, keeping it as the last node of the current list.

return head.next;

• head.next points to the actual start of the resulting list (skipping the dummy node).
• This ensures the dummy node itself is not part of the returned list.

This solution efficiently adds two numbers represented as linked lists, handling digit-by-digit addition and carry-over. By using a dummy head node and a tempNode pointer, the implementation simplifies list operations and ensures the resulting list is correctly formed without extra edge-case handling. This method, while straightforward, is effective and serves as a solid introduction to linked list manipulations and basic arithmetic operations in an algorithmic context.