[LeetCode] Snapshot Array

Problem: Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
• void set(index, val) sets the element at the given index to be equal to val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
• int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Constraints:

• 1 <= length <= 5 * 10^4
• 0 <= index < length
• 0 <= val <= 10^9
• 0 <= snap_id < (the total number of times we call snap())
• At most 5 * 10^4 calls will be made to set, snap, and get.

Approach: First thing in the problem we can notice that we can't save full array, every time we take the snapshot as the length of the array could be 5 * 10 ^ 4 and snap can be called 5 * 10 ^ 4 times.

What we can do is we only store the updates which happened in the current snapshot. In this way for every index we will have a list of snapshot id and the value updates so now when we try to get the value given the snapshot we can do following:

• If no modification i.e. list of updates at the input index will be  null or if no snapshot is taken i.e. current snapshot id is still 0 then we can simply return 0.
• Else we find the upper bound of snap_id using binary search and return the stored value.

That's all!

Implementation in C#:

public class SnapshotArray

{

    public SnapshotArray(int length)

    {

        this.snapshots = new List<Tuple<int, int>>[length];

        this.currSnapId = 0;

    }

   

    public void Set(int index, int val)

    {

        if (this.snapshots[index] == null)

        {

            this.snapshots[index] = new List<Tuple<int, int>>();

        }

        int length = this.snapshots[index].Count;

        if (length > 0 &&

            this.snapshots[index][length - 1].Item1 == this.currSnapId)

        {

            this.snapshots[index].RemoveAt(length - 1);

        }

        this.snapshots[index].Add(new Tuple<int, int>(this.currSnapId,

                                                      val));

    }

   

    public int Snap()

    {

        ++this.currSnapId;

        return this.currSnapId - 1;

    }

   

    public int Get(int index, int snap_id)

    {

        // No modification or no snapshot taken

        if (this.snapshots[index] == null || this.currSnapId == 0)

        {

            return 0;

        }

        int snapIndex = this.FindSnapIndex(this.snapshots[index], snap_id);

        return snapIndex == -1 ?

               0 :

               this.snapshots[index][snapIndex].Item2;

    }

    private int FindSnapIndex(List<Tuple<int, int>> snapIds, int snapId)

    {

        int start = 0, end = snapIds.Count - 1;

        if (snapId >= snapIds[end].Item1)

        {

            return end;

        }

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            int currSnap = snapIds[mid].Item1;

            if (currSnap == snapId)

            {

                return mid;

            }

            else if (currSnap < snapId)

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return end;

    }

    private List<Tuple<int, int>>[] snapshots;

    private int currSnapId;

}

Complexity: SnapshotArray: O(1), Set: O(1), Snap: O(1), Get: O(logn) 

[LeetCode] Time Based Key-Value Store

Problem: Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

• TimeMap() Initializes the object of the data structure.
• void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
• String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

Example:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

Constraints:

• 1 <= key.length, value.length <= 100
• key and value consist of lowercase English letters and digits.
• 1 <= timestamp <= 10^7
• All the timestamps timestamp of set are strictly increasing.
• At most 2 * 10^5 calls will be made to set and get.

Approach: This is a binary search problem where we need to find the timestamp which is equal to or just smaller than the given timestamp. 

Given the constraint that timestamps are coming in strictly increasing order, we don't have to sort or maintain a sorted data structure. We can simply use a list.

Implementation in C#:

public class TimeMap

{

    public TimeMap()

    {

        this.kvMap = new Dictionary<string, List<Tuple<int, string>>>();

    }

   

    public void Set(string key, string value, int timestamp) {

        if (!this.kvMap.ContainsKey(key))

        {

            this.kvMap[key] = new List<Tuple<int, string>>();

        }

        this.kvMap[key].Add(new Tuple<int, string>(timestamp, value));

    }

   

    public string Get(string key, int timestamp)

    {

        if (!kvMap.ContainsKey(key))

        {

            return "";

        }

        int index = this.GetIndex(kvMap[key], timestamp);

        return index == -1 ?

               "" :

               kvMap[key][index].Item2;

    }

    private int GetIndex(List<Tuple<int, string>> sortedTimestamps,

                         int timestamp)

    {

        int start = 0, end = sortedTimestamps.Count - 1;

        if (start > end || timestamp < sortedTimestamps[0].Item1)

        {

            return -1;

        }

        while (start <= end)

        {

            int mid = start + (end - start) / 2;

            int currTimestamp = sortedTimestamps[mid].Item1;

            if (currTimestamp == timestamp)

            {

                return mid;

            }

            if (currTimestamp < timestamp)

            {

                start = mid + 1;

            }

            else

            {

                end = mid - 1;

            }

        }

        return end;

    }

    private Dictionary<string, List<Tuple<int, string>>> kvMap;

}

Complexity: Set - O(1), Get - O(logn)

[LeetCode] Count Negative Numbers in a Sorted Matrix

Problem: Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Example:

Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.

Input: grid = [[3,2],[1,0]]
Output: 0

Approach: Given we have a matrix which is sorted row wise and column wise, we can use the approach which we have used in the problem of searching an element in row wise and column wise sorted matrix.

Here, I am going to start from bottom left corner as the matrix is sorted in descending order but we can solve this problem starting from top right corner too.

Implementation in C#:

    public int CountNegatives(int[][] grid)

    {

        int rows = grid?.Length ?? 0;

        if (rows == 0)

        {

            return 0;

        }

        int cols = grid[0].Length;

        int row = rows - 1, col = 0;

        int totalNegNums = 0;

        while (row >= 0 && col < cols)

        {

            if (grid[row][col] < 0)

            {

                totalNegNums += (cols - col);

                --row;

            }

            else

            {

                ++col;

            }

        }

        return totalNegNums;

    }

Complexity: O(m + n)

[LeetCode] Search Insert Position

Problem: Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Example:

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

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

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

Constraints:

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums contains distinct values sorted in ascending order.
• -10^4 <= target <= 10^4

Approach: The problem here is just to find the target itself or just greater element in the array so if you see this is a binary search problem with following changes:

1. If nums[mid] < target then obviously we need to go to the right side i.e. start = mid + 1
2. Else end = mid
3. Return end.

Implementation in C#:

    public int SearchInsert(int[] nums, int target)

    {

        int start = 0, end = nums.Length - 1 ;

        if (target < nums[start])

        {

            return start;

        }

        if (target > nums[end])

        {

            return end + 1;

        }

        while (start < end)

        {

            int mid = start + (end - start) / 2;

            if (nums[mid] < target)

            {

                start = mid + 1;

            }

            else

            {

                end = mid;

            }

        }    

        return end;

    }

Complexity: O(log(n))

[LeetCode] Find Smallest Letter Greater Than Target

Problem: You are given an array of characters letters that is sorted in non-decreasing order, and a character target. There are at least two different characters in letters.

Return the smallest character in letters that is lexicographically greater than target. If such a character does not exist, return the first character in letters

Example:

Input: letters = ["c","f","j"], target = "a"
Output: "c"
Explanation: The smallest character that is lexicographically greater than 'a' in letters is 'c'

Input: letters = ["c","f","j"], target = "c"
Output: "f"
Explanation: The smallest character that is lexicographically greater than 'c' in letters is 'f'.

Input: letters = ["x","x","y","y"], target = "z"
Output: "x"
Explanation: There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].

Constraints:

• 2 <= letters.length <= 10^4
• letters[i] is a lowercase English letter.
• letters is sorted in non-decreasing order.
• letters contains at least two different characters.
• target is a lowercase English letter.

Approach: This is a simple binary search problem with following changes:

1. If letters[mid] <= target then obviously we will search on the right side so start becomes mid + 1.
2. Else we go to the left to see there is a smaller letter which is greater than target so end becomes mid.
3. In the end we return letters[end]

Implementation in C#:

    public char NextGreatestLetter(char[] letters, char target)

    {

        int start = 0, end = letters.Length - 1;

        if (target < letters[start] || target >= letters[end])

        {

            return letters[start];

        }

        while (start < end)

        {

            int mid = start + (end - start) / 2;

            if (letters[mid] <= target)

            {

                start = mid + 1;

            }

            else

            {

                end = mid;

            }

        }

        return letters[end];

    }

Complexity: O(log(n))

[LeetCode] 2 Keys Keyboard

Problem: There is only one character 'A' on the screen of a notepad. You can perform one of two operations on this notepad for each step:

• Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
• Paste: You can paste the characters which are copied last time.

Given an integer n, return the minimum number of operations to get the character 'A' exactly n times on the screen.

Example:

Input: n = 3
Output: 3
Explanation: Initially, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.

Input: n = 1
Output: 0

Approach: We are going to use bottom-up DP here. We can define a 1D array where table[i] tells the minimum number of steps required to display i A's. Obviously table[n] will be our answer.

Now the main logic here is to get the relations between table[i] and table[i-1]...table[1], right?  Let's understand it; let's say we had j A's on the screen where 1 <= j < i. Now we can say we can copy these j A's and paste it exactly (i - j) / j times to display i A's so total number of operations will be:

f(i) = f(j) + 1 + (i - j) / j

Why? Let's see:

• f(j) - Number of steps to display j A's
• 1 - Copy All
• (i - j) / j - Number of pastes.

Now let's simplify this equation:

f(i) = f(j) + 1 + (i - j) / j

=> f(i) = f(j) + 1 + (i/j) - (j/j)

=> f(i) = f(j) + 1 + (i/j) - 1

=> f(i) = f(j) + i / j

So here is our final relation:

f(i) = f(j) + i / j

We also need to make sure that i should be divisible by j as it's kind of repeated pastes. Now we just need to get the minimum of all such j's where 1 <= j < i and i is divisible by j.

That's all!

Implementation in C#:

    public int MinSteps(int n)

    {

        if (n <= 1)

        {

            return 0;

        }

        int[] table = new int[n + 1];

        for (int i = 2; i <= n; ++i)

        {

            table[i] = int.MaxValue;

            for (int j = 1; j <= i / 2; ++j)

            {

                if (i % j != 0)

                {

                    continue;

                }

                table[i] = Math.Min(table[i], table[j] + i / j);

            }

        }

        return table[n];

    }

Complexity: O(n^2)

[LeetCode] Minimum Number of Pushes to Type Word II

Problem: You are given a string word containing lowercase English letters.

Telephone keypads have keys mapped with distinct collections of lowercase English letters, which can be used to form words by pushing them. For example, the key 2 is mapped with ["a","b","c"], we need to push the key one time to type "a", two times to type "b", and three times to type "c" .

It is allowed to remap the keys numbered 2 to 9 to distinct collections of letters. The keys can be remapped to any amount of letters, but each letter must be mapped to exactly one key. You need to find the minimum number of times the keys will be pushed to type the string word.

Return the minimum number of pushes needed to type word after remapping the keys.

An example mapping of letters to keys on a telephone keypad is given below. Note that 1, *, #, and 0 do not map to any letters.

Example:

Input: word = "abcde"
Output: 5
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
Total cost is 1 + 1 + 1 + 1 + 1 = 5.
It can be shown that no other mapping can provide a lower cost.

Input: word = "xyzxyzxyzxyz"
Output: 12
Explanation: The remapped keypad given in the image provides the minimum cost.
"x" -> one push on key 2
"y" -> one push on key 3
"z" -> one push on key 4
Total cost is 1 * 4 + 1 * 4 + 1 * 4 = 12
It can be shown that no other mapping can provide a lower cost.
Note that the key 9 is not mapped to any letter: it is not necessary to map letters to every key, but to map all the letters.

Input: word = "aabbccddeeffgghhiiiiii"
Output: 24
Explanation: The remapped keypad given in the image provides the minimum cost.
"a" -> one push on key 2
"b" -> one push on key 3
"c" -> one push on key 4
"d" -> one push on key 5
"e" -> one push on key 6
"f" -> one push on key 7
"g" -> one push on key 8
"h" -> two pushes on key 9
"i" -> one push on key 9
Total cost is 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 1 * 2 + 2 * 2 + 6 * 1 = 24.
It can be shown that no other mapping can provide a lower cost.

Constraints:

• 1 <= word.length <= 10^5
• word consists of lowercase English letters

Approach:  If you see, we can only use 8 keys (2, 3, 4, ..., 9) in total that means we can type only 8 characters with one push each, then 8 characters with two pushes each and so on so the optimal way to map charaters to keys evenly.

Given the above facts we can see that it's clearly a greedy problem where we need to start with most frequent characters in sorted and try to give the minimum numnber of pushes to those characters so that we can reduce the number of pushes as much as possible.

What we can do is, we can sort the given word as per the frequency of characters in descending order. Now we can use following simple steps:

• charsAtCurrLevel = 1
• currPushes = 1
• totalPushes = 0
• i = 0
• WHILE i < n:
• totalPushes = totalPushes + Count of word[i] * currPushes
• charsAtCurrLevel = charsAtCurrLevel + 1
• IF charsAtCurrLevel > 8
• currPushes = currPushes + 1
• charsAtCurrLevel = 1
• i = i + Count of word[i]
• RETURN totalPushes

This will solve the problem in nlogn time which is good but let's see how we can improve it. As such we can't do anything but what we can do is use of constraint 2 where the string characters are only small lowercase english characters. Let's see how;

Instead of using map for collecting frequency, we can use integer array of size 26. Once we collect all the frequency, we can now sort this frequency array in descending order. Now we know every index in this frequency array is representing a character in word string so we can use following steps to calculate total pushes:

• totalPushes = 0
• currPushes = 1
• FOR i = 0 To 26
• IF freqMap[i] == 0
• BREAK
• IF i % 8 == 0
• currPushes = currPushes + 1
• totalPushes = totalPushes + freqMap[i] * currPushes
• RETURN totalPushes

 That's all!

Implementation in C#:

Approach 1: Sort word based on frequency of characters:

    public int MinimumPushes1(string word)

    {

        int length = word?.Length ?? 0;

        if (length <= 8)

        {

            return length;

        }

        var wordArr = word.ToCharArray();

        int[] map = new int[26];

        foreach (char ch in wordArr)

        {

            ++map[ch - 'a'];

        }

        Array.Sort(wordArr, (c1, c2) => {

            if (map[c2 - 'a'] == map[c1 - 'a'])

            {

                return c1.CompareTo(c2);

            }

            return map[c2 - 'a'].CompareTo(map[c1 - 'a']);

        });

        int totalPushes = 0;

        int currReqdPushes = 1;

        int distintCharsAtCurrLevel = 1;

        for (int i = 0; i < length; )

        {

            totalPushes += map[wordArr[i] - 'a'] * currReqdPushes;

            ++distintCharsAtCurrLevel;

            if (distintCharsAtCurrLevel > 8)

            {

                distintCharsAtCurrLevel = 1;

                ++currReqdPushes;

            }

            i += map[wordArr[i] - 'a'];

        }

        return totalPushes;

    }

Approach 2: Sort frequency array:

    public int MinimumPushes(string word)

    {

        int length = word?.Length ?? 0;

        if (length <= 8)

        {

            return length;

        }

        var wordArr = word.ToCharArray();

        int[] map = new int[26];

        foreach (char ch in word)

        {

            ++map[ch - 'a'];

        }

        Array.Sort(map, (i1, i2) => {

            return i2.CompareTo(i1);

        });

        int totalPushes = 0;

        int currReqdPushes = 1;

        for (int i = 0; i < 26; ++i)

        {

            if (map[i] == 0)

            {

                break;

            }

            if (i != 0 && i % 8 == 0)

            {

                ++currReqdPushes;

            }

            totalPushes += map[i] * currReqdPushes;

        }

        return totalPushes;

    }

Complexity: Approach 1: O(nlogn)

                      Approach 2: O(n)