Design Youtube

Problem: Design a highly scalable video on demand (VOD) streaming platform.

Requirements:

Before we jump into requirements, we should realize we have two different types of users:

• Content creators
• Viewers

If we try to observe how they use our platform, we can see the requirements are different both functional as well as nonfunctional requirements.

1. Functional requirements:

a. Content creators:

1. Upload any format/codec video.
• Once the video is uploaded, it can be deleted but not be modified.
2. Each video should have metadata:
• Mandatory: title, author, description.
• Optional: List of categories / tags.
• Metadata can be updated anytime.
3. Get an email notification when the video is available publically.
4. Live streaming is not supported.

b. Viewers:

1. Only registered users can view the content.
2. Can search using free text in all of video metadata.
3. Can watch vidoes on any kind of device (desktop / phone / TV) and network conditions.

2. Nonfunctional requirements:

a. Content creators:

1. Scalability:
• Thousands of content creators.
• Upload 1video/week per creator
• Average video size ~50 GB (50 TB / week)
2. Consistency:
• We prefer to have consistency here over availability.
3. Availability:
• 99.9 percentile
4. Performance:
• Response time of page load < 500 ms at 99 percentile.
• Video becomes available to view in hours.

b. Viewers:

1. Scalability:
• 100K-200K daily active users
2. Availability:
• 99.99 percentile
3. Performance:
• Search results and page loads < 500 ms at 99 percentile
• Zero buffer time for video play

Design:

Step 1: API design:

As usual, for the api design let's first translate our functional requirements in a sequence diagram which should look like follows:

Now we can easily identify the entities and URIs using above sequence diagram:

• Users
• /users
• Videos:
• /videos
• /videos/{video_id}
• Search:
• /search

Now let's put HTTP method:

• Users:
• POST /users: Create / register user
• POST /users/login: Login a user
• Videos:
• POST /videos: Start upload a data
• PUT /videos/{video_id}/metadata: Create/update metadata of video
• GET /videos/{video_id}: Get the video url
• POST /videos/{video_id}/play: Send the video content to client
• DELETE /videos/{video_id}: Delete a video
• Search:
• GET /search

Step 2: Mapping functional requirements to architectural diagram:

a.1 Content creator can upload any format/codec video:

b.3 Viewers can watch video on any device and at different network conditions:

I am taking both of these requirements together as these are inter related. We need to upload any video in such a manner that it can be supported on any device and adapted to different network conditions to view.

Let's first understand what is a video file. 

The video file is a container which contains:

• Video stream
• Audio stream
• Subtitles
• Metadata like codec, bitrate, resolution, frame rate

The binary representation of these containers like mpg/avi/mp4 can be different based on how these streams are encoded and algos to encode and decode these streams are called codecs like H.264 or AV1 or VP9 etc.

The video captured using a camera is encoded based on lossless compression algorithm which makes it suitable for professional editing but it is too big in size so this kind of codec is not suitable for streaming and storage at scale so the first step is too apply a lossy compression algorirthm. This method of converting a encoded stream to a different encoded stream is called Transcoding.

Size of a video = Bit rate (bits/second) * Video length (seconds)

So this is obvious that we need to reduce the bit rate in order to reduce the size of video but given that we need to support different devices and different network bandwidth. We can't depend on only one bit rate. We need to support multiple outputs file supporting different bit rates which is directly proportonal to resolutions. The standard resolutions are 360p, 640p, 720p, 1080p and 4K.

This will partially take care of supporting multiple devices but it won't support varying network conditions like home network getting used by multiple users or the user is travelling. To support this requirement, we will use technique called Adaptive bit rate or Adaptive streaming.

In Adaptive streaming, we break our stream into multiple small chunks of size say 5 seconds or 10 seconds. We put references to all of these streams in a text file called manifest(mpd). When player tries to play the video. It first download this manifest file and then choose a default resolution (say 720p) and play it's say first 4-5 chunks to analyze how the network conditions are. If the network conditions are better it switches to better resolution say 1080p or even 4K. It there are download delays then it goes for lesser resolution chunks. Player keeps analysing the chunks download speed to decide which resolution to go for.

The next step is to fully support every kind of devices. For this we need to package our video content to support different streaming protocols. Different OS / browser supports different protocols. Here we can also apply DRM(Digital Rights Management) to protect our video in order to support FR# b.1 Only registered users can watch the video. Using DRM we can also support subscrption when we want to intoduce it.

Now if you see there are steps which we need to take in order to upload the video and making it available for different devices and different locations / network bandwidth. We will use pipes and filter pattern here to support it. 

We will have a Video service as public interface for this whole activity. This service will have it's own DB which is NoSql DB in order to support fluid schema. So here is the flow of video upload:

1. Content creator call Video service to upload video.
2. Video service will start the upload to object store asynchronously and save the metadata into it's DB and return the confirmation to user with video id.
3. Once the video upload is complete to object store, it queues this message to a new service Transcoding service.
4. Transcoding service first convert this video to 5-10 seconds chunks and transcode each chunk into multiple resolution and upload it into it's object store. It also generates manifest file for adaptive streaming.
5. Transcoding service now queue the message to new service say Packaging service.
6. Packaging service package these streams according to streaming protocols and save it into it's own object store.
7. Package service now queue the video_id and video_url(which is ultimately manifest download) back to Video service and video service updates it's DB using the video_id.  

We can debate over a point on Transcoding service where we can propose a new service to break the uncompressed video in chunks, queue these chunks to let transcoding service just transcode these chunks in parallel. But that's what we can achieve using multithreading in the transcoding service itself. In that way it will be much easiser to debug issues and also much easier to support the restartabilty as all these chunkings and transcoding will happen in just one service.

We can support FR# a.3 Notify creatore when video is publically available here only by adding a new service say Notification service. Video service will queue the video details to this service. Notification service now can send the notification (email) to content creator.

With this knowlege let's see how our architectural diagram looks like.

a.2 Update the video metadata:

a.1 Delete the video:

User can simply call the video service to perform these opeations so now here is how the diagram looks like

b.2 Viewer can search for the video against the video metadata:

To support search we need to have a different service say Search service whose DB is optimized for search like Elastic search. Video service can queue the metadata to this service so you can assume it will also become the part of video upload / update of metdata / deletion of metadata. 

We also need to use pagination here.

b.3. Watch video on any device:

We have already done enough to support this requirement. Client first need to call Video service to get the video_url. Client then downloads the manifest file and then client/player will directly stream the chunks of video from object store as per adaptive streaming which I have already explained.

 So now we are done with every functional requirement we have.

Step 3: Mapping non functional requirements to architectural diagram:

a.1 Content creator scalability:

There is not much to do in terms scalability for the first scalability requirement as the frequency of video upload is not much (1/week/user) That means ~10K video uploads in a week. However it can happen that at a particular time we can get thousands of upload requests. To support those we can have multiple instances of Video service and Web app service. 

To tackle the video size we have already created a pipeline to compress the video size but there is still one problem; 

If we take the whole video content to first video service and then upload it to object store, this whole process will consume lot's of resources and as it can take hours to upload uncompressed video, we might end up scaling video service too much. 

To resolve the problem we can use presigned urls of object store. Presigned urls are the urls with limited permissions and limited time. With presigned urls, the flow of video upload looks like as below:

1. Client send request for video upload to video service.
2. Video service requests presigned url from object store with it's own permissions.
3. Send the presigned url as response of video upload API to the client.
4. Client now directly upload the video to object store using presigned url. 
5. Rest of the pipeline remains same.

With this flow, we can see Video service doesn't have to scale and we will save lot's of resources so now with these changes here is how architecture diagram looks like:

a.2 Content creator availability:

We have already take care of the availabity using the multiple instances of web app and video services. We can use the cloud native services for video transcoding and packaging like AWS Elemental MediaConvert and AWS Elemental MediaPackage to support the availability.

We can replicate the Video service DB to support the availability.

a.3 Content Creator Performance:

We have already taken care of the performance as there is not much to do. However the only problem is when all/many content creators try to upload videos at the same time. In such scenario, we might not able to complete the video upload pipeline in hours. 

We need to parallelize this process. That means we need to have multiple instances of Transcoding service and Packaging service.

a.4 Content Creator CP over AP:

To achieve this we just need to choose the right Video service DB or DB's configuration which supports consistency over availability. That's all!

b.1 Viewers Scalability:

To support this 100K - 200K user visits we have already scale our web app service and video service but to scale the search functionality, we need to have multiple instances of search service. This will take care of the scalabilty of service. 

As elastic search is not cloud native, we can use AWS opensearch / Elastic cloud on AWS which autoscale itself.

b.2 Viewers Availability: 

We have done mostly everything for the availability but as here our availability requirement is high. We can use muti region deployment and a global load balancer too. This will also help with the performance.

b.3. Viewers Performance:

We are using adaptive bitrate streaming for the zero buffer time but as you see still we need to download intial chunks, we need to go to object store which might be expensive so we can use CDN to provide it. We can have initial chunks in the CDN to increase the performance of download and then the client can use adaptive streaming to go for the right chunks.

Please note that we can put the whole video too on the CDN which will definitely improve the performance and the quality of the video but it can be very expensive so I am still opting for initial chunks of videos.

 

b.4. Viewer AP over CP:

We are already using lot's of async operations / message broker which guarantees availability but eventual consistency. For search we are already receiving metadata updates using queue and also Elastic search provides AP over CP so this requirement is already satisfied.

With this we are done with every functional and non functional requirements and here is how our final architectural diagram looks like:

That's all!

* Please note that here we should have a User service to support user login and registration but that's very obvious so I have not discussed it here. Given the user's volume is in hundreds of thousand, we don't need to do many things.

Design Instagram

Problem: Design highly scalabale image sharing social media platform like instagram.

Requirements:

1. Functional Requirements:

1. Only registered user can access the platform. They need to provide following info while registering:
• Mandatory: first name, last name, email, phone number, profile image, password
• Optional: age, sex, location, interests etc.
2. User can share/post only images
• We need to design it in a way to extend it to videos or text.
3. Search a user using different attibutes
4. Unidirectional relationship: User A follows User B does not mean User B also follows User A.
5. Load a timeline of latest images posted by people they follow sorted by recency in descending order

 

2. Non-functional Requirements:

1. Scalability:
• ~1-2 billion active users
• 100-500 million visits / day
• Each user uploads ~1 image / day
• Each image size ~2 MB.
• Data processing volume: ~1 PB / day
2. Availability: Prioritize availability over consistency as it is okay even if user does not see the latest data. We are targetting 99.99% here.
3.  Performance: 
• Response time < 500 ms at 99 percentile.
• Timeline load time <1000 ms at 99 percentile.

Design:

Step 1: API design:

For the api design, let's first translate our functional requirements in a sequence diagram which should look like follows:

Now if you see above, we can easily identify the entities and URIs:

• Users
• /users
• /users/{user-id}
• Images
• /images
• /images/{image-id}
• Search
• /search

Now let's put HTTP methods:

• Users 
• POST /users - Create user / register user
• POST /users/login - Login a user
• POST /users/{user-id}/follow - Follow a user
• DELETE /users/{user-id}/follow - Unfollow a user
• GET /users/{user-id}/timeline - Get user time line. This requires pagination.
• Images
• POST /images - Post an image
• GET /images/{image-id} - Get an image
• Search
• Get /search - Search a user

Step 2: Mapping functional requirements to architectural diagram:

Before we move to our main functional requirements, I want to add a service say "Web app service" to serve the html pages since we have support on desktop web browser too.

1. Registering user to our platform:

We will have a User service with it's own DB which will help with login and registration of users. User service database will have following fields as per FR#1:

• user_id
• user_name
• first_name
• last_name
• email
• password
• phone_number
• profie_image_url
• and some optional fields like age, sex, interests, location etc.

If you see we have so many optional fields which can change with time like some optional fields can be removed and some can be added. That means our schema is fluid and that's why we are going with NoSql Document DB. Given we have around ~1-2 billions users, these schma changes become an considerable overhead.

In the schema we are storing the profile image url instead of profile image because DBs are not optimized for blob storage so what we will do is we will store the profile image into a blob store or object store and then save the image url in our DB.

Once the registration is completed, client will get user id and auth token which will help client with further operations.

2. Post an image:

Let's have a post service for this service, we are not calling it as image service so that we can extend it to any type of post. This service will have it's own DB which contains the following fields:

• post_id
• user_id
• post_url
• timestamp
• post_type - This will be by default image but can be extended to video etc.

Since this is a fixed schema, I am going to use SQL DB for storing this info. Here is the flow of image upload:

1. User send the request to Post service to share an image
2. Post service send the image to object store
3. Object store return the url of uploaded image
4. Save the image metdata and url in the DB
5. Return confirmation to user.

3. Search users using different attributes:

We can use the same user service to search the users but if you see this DB is not optimized for search As we don't know in advance what all the attributes are searchable or what kind of search we are going to support, it's better if we use a different service say Search service with DB which is optimized for search scenario like elastic search or other lucene based DB.

So now whenever there is a new user added or there is an update in user's record we can queue it to the search service. Search service will updates it's DB. 

4.: Follow/Unfollow user:

We can create another service to handle follow/unfollow activity but for me it's not that much useful and is unnecessary. We can use existing User service only, we just need to create another collection with following fields:

1. follower_user_id
2. target_user_id 
3. target_user_name

5. Loading the timeline of the user:

That's the most complex problem. Within the current design here is how we can achieve it.

• Client send the request to User service
• User service gets all the users who the user is following.
• It will then query the posts of all the users sorted by timestamps with pagesize of 20-50 using the Post service.
• Send page size number of posts sorted based on timestamp to the client.
• Client can then dowload the images using the post_urls from object store.

This will definitely solve the problem but it is very inefficient. I know we are not solving the non-functional requirements now but we should think about the performance.

To make it efficient, we will use CQRS pattern. We will have a new service called Timeline service. This will have an efficient key value pair DB where key is the user_id and value is the list of post records of all the users followed by the user with user_id(key). Every post record will have {post_url, user_id, timestamp}

Now here is what we do with this new service:

• POST service will queue the new posts containing post_url, user_id, timestamp to Timeline service.
• Timeline service will take the user_id and get it's followers from User service.
• It then add this post to the front of all the followers' list of post records. It can remove the posts if the list is have more records than what we need to show in the timeline.

With this new service, our flow of showing timeline will become straight forward:

• Client requests Timeline service for the timeline.
• Timeline service returns the list of post records from it's key value db with key as requested user's user_id.
• Now client can download the images from object store using post_url.

This will be eventual consistent but that's okay as per our non functional requirements. This will be much efficient than the older design.

Step 3: Mapping nonfunctional requirements to architectural diagram:

1. Scalability: 

If you see we have following scalability requirements here:

• Number of users: We have 1-2 billion users data which will be huge so we can't rely on just one DB instance so we have to shard the User service DB. We can shard using hashing technique:
• User DB: Shard on the basis of user_id.
• Follower DB: Shard based on target_user_id as our main case is to get the followers which is a call from Timeline service.
• For search we are already using elastic search and we can shard it too.
• Number of visists: To support these number of visits, we have to run multiple instances of different services behind load balancer.
• Number of posts: This has two parts:
1. Data in the DB: This will be huge also so we have to shard Post DB as well as Timeline DB. Post DB can be sharded using post_id and Timeline DB using user_id.
2. Image Data: As per requirement we need to save petabytes of data because we are getting uncompressed image. Not only these images will take lots of space but also these are not optimized for viewing on Mobile device or browser. We can introduce an async image processing pipeline like AWS severless image handler to compress these images which will convert this petabytes of data into TBs or even GBs.

2. Availability:

By using multiple instances of our services behind load balancer, we have almost achieved the availability. We can have replicas of our DBs to achieve the availability requirements. Additionally we can do multi region deployement and have a global load balancer in case one region is down. It will also increase the performance.

3. Performance:

We have two performance benchmarks:

• 500 ms for every page load: To achieve it we can use CDNs to store html pages, CSS and post images.
• 1 second for timeline page load: We have already made a decision to use CQRS pattern and made Timeline service to serve the timeline page. This will take care of the performance part but it will create a different problem. There are few thousands of users whom we call celebrity / influencers and millions of users follow them. In case if a celebrity user makes a post, millions of entries of Timeline service DB will be updated which might slow down the DB and hence the performance. To tackle this situation we can make following steps:
1. Define which user is celebrity; Say a celebrity has 1 M followers.
2. Make a column in User DB - IsCelebrity which will tell if the user is a celebrity or not.
3. When celebrity post an image and Timeline serivec calls User service to get the followers list. Instead of returning followers list, User service will return IsCelebrity = true.
4. Another Key-Value pair say Celebrity POST DB will be added to Timeline service DB which where key is celebrity_user_id and value is sorted list of post records.
5. When Timeline service receive IsCelebrity as true. It just add the post into Celebrity POST DB.
6. While loading the Timeline, Time line service get the list of celebrities from User service which the user is following using new REST endpoint on User service say GET /users/{user-id}/celebrity.
7. Timeline service then merge the sorted results it gets from celebrity key value pair and user key value pair and returns it to user.

And that's all about the performance. Now that we have addresses every requirement functional or non functional, here is our final architecture diagram:

Have fun!

[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))