# Two Sum: Input array is sorted

957 views

Similar to Question [1. Two Sum], except that the input array is already sorted in ascending order.

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 = , l2 = 
Output: ```

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]```

Farjanul Nayem Answered question July 27, 2022
0

Of course we could still apply the [Hash table] approach, but it costs us O(n) extra space, plus it does not make use of the fact that the input is already sorted.

O(n log n) runtime, O(1) space – Binary search:
For each element x, we could look up if target – x exists in O(log n) time by applying binary search over the sorted array. Total runtime complexity is O(n log n).

Solution in Java

```public class Solution {
// example in leetcode book
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p = l1, q= l2, curr = dummyHead;
int carry = 0;
while (p != null || q!= null) {
int x = (p != null) ? p.val : 0;
int y = (q != null) ? q.val : 0;
int digit = carry + x + y;
carry = digit / 10;
curr.next = new ListNode(digit % 10);
curr = curr.next;
if (p != null) p = p.next;
if (q != null) q = q.next;
}
if (carry > 0) {
curr.next = new ListNode(carry);
}
}
}```

Solution in Python

```class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None```

```class Solution(object):
carry = 0
while l1 or l2:
val = carry
if l1:
val += l1.val
l1 = l1.next
if l2:
val += l2.val
l2 = l2.next
curr.next = ListNode(val % 10)
curr = curr.next
carry = int(val / 10)
if carry > 0:
curr.next = ListNode(carry)