programming

#5 Valid anagram

Posted by

1

https://leetcode.com/problems/valid-anagram/

For two strings to be anagrams, their lengths must be equal and every character must appear in each string for the same ‘count’.

We can convert the strings to character arrays and then sort them. If the two sorted arrays are equal (remember array’s are value types in Swift) – the strings must be anagrams. This would be a O(n logn) time and O(n) space solution (sorting using the standard library in swift takes O(n) space)

The other solution uses a Map to record the count of each character in the source string and then iterates over the target string to check if every character can be mapped to a character in source string -> as we iterate over target, we also need to update the map to reduce the count of ‘seen’ characters. We also need to be sure to have lengths equal check before we get into the loop – otherwise we could have a scenario where the source string has a character that is not needed by the target string -> in this case we need to return false.

2 Sum

Posted by

2

https://leetcode.com/problems/two-sum

Probably the first problem you solved when you started leetcoding.

This is a classic problem – I haven’t been asked this problem ever in an interview – but this one brings back a lot of memories and yes there was a time I struggled to solve this problem as well 🙂

Using 2 loops would be the most straightforward but slow way to solve this problem – in an interview, the interviewer will expect a better solution that O(N^2) though.

The optimal solution uses a hashmap to keep the index of previously seen numbers – this increases the space complexity to O(n), but improves the time complexity to O(n).

Variant: Although this problem asks for the index of the two numbers that add up to target – there is a variant of this problem that asks for the actual numbers itself (i.e. find the two numbers that add to target). That variant can be solved in O(n logn) time, if we cannot/do-not want to allocated O(n) space – that solution first sorts the input array and then iterates over the sorted array with two pointers – increasing the left pointer if the sum is smaller and reducing the right pointer if the sum is larger than the target.

If you just solved this problem on your own – welcome to leetcoding, you have an exciting journey ahead of you.