Leetcode #67 and avoiding edge cases

I often see a typical solution for leetcode #67 Add Binary:

public string AddBinary(string a, string b)
{
var sb = new StringBuilder();

int iA = a.Length - 1;
int iB = b.Length - 1;
int carry = 0;
while (iA >= 0 || iB >= 0)
{
int bA = iA < 0 ? 0 : a[iA] - '0';
int bB = iB < 0 ? 0 : b[iB] - '0';

sb.Insert(0, (bA + bB + carry) % 2);

carry = (bA + bB + carry) / 2;

iA--;
iB--;
}

if(carry == 0)
return sb.ToString();

sb.Insert(0, '1');
return sb.ToString();
}

It’s clear, easy-to-understand and it looks like we cannot improve this code anymore.

The edge case when iA == 0 and iB == 0 is very important if carry is 1 (for example when we sum 1and 1 and we insert 0 to sb but carry is 1). But can we unify this?

Yes, we can:

public string AddBinary(string a, string b)
{
var sb = new StringBuilder();
int iA = a.Length - 1;
int iB = b.Length - 1;
int carry = 0;
while (iA >= 0 || iB >= 0 || carry > 0)
{
int bA = iA < 0 ? 0 : a[iA] - '0';
int bB = iB < 0 ? 0 : b[iB] - '0';
sb.Insert(0, (bA + bB + carry) % 2); carry = (bA + bB + carry) / 2; iA--;
iB--;
}
return sb.ToString();
}

You should try to avoid edge cases when possible! If you see an edge case think twice can you generalize your code? Sometimes it’s easy, sometimes not.

A trivial example is a such solution for leetcode #9 Palindrome Number:

public bool IsPalindrome(int x)
{
if(x == 0)
return true;

if(x < 0)
return false;

if(x % 10 == 0)
return false;

int revertedNumber = 0;
while(x > revertedNumber)
{
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}

return x == revertedNumber || x == revertedNumber/10;
}

This solution works fine and passes all tests. But it’s suboptimal.

What if we have a negative number? In such case we have revertedNumber = 0 and x < 0, hence we don’t step into while section. Also, neither x == revertedNumber or x == revertedNumber / 10. So, we can safely remove this check:

    if(x < 0)
return false;

And the solution will work as well as previous.

The published solution also contains this check.

Maybe, here is logic ‘avoid creating variables and running code` (early exit). Yes, this can be a reason.

Another example is harder. You can solve leetcode 203 Remove Linked List Elements iteratively:

public ListNode RemoveElements(ListNode head, int val)
{
while (head != null && head.val == val)
head = head.next;

var node = head;

while (node != null && node.next != null)
{
if (node.next.val == val)
node.next = node.next.next;
else
node = node.next;
}

return head;
}

Our start step is to ‘rewind’ the linked list to the first element with a given val. But we can omit this step if we attach a node before the list:

public ListNode RemoveElements(ListNode head, int val)
{
var dummy = new ListNode(val);
dummy.next = head;
var curr = dummy;

while (curr.next != null)
{
if (curr.next.val == val)
curr.next = curr.next.next;
else
curr = curr.next;
}

return dummy.next;
}

What is better here: handle edge case or avoid it? Choose yourself!

Do you know any other examples of how to avoid edge cases? If yes, just post it in the comments!

Software Engineer