binary search – My Programming Notes

Tag Archives: binary search

C# || How To Find The Minimum Speed To Arrive On Time Using C#

September 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the minimum speed to arrive on time using C#.

1. Min Speed On Time – Problem Statement

You are given a floating-point number hour, representing the amount of time you have to reach the office. To commute to the office, you must take n trains in sequential order. You are also given an integer array dist of length n, where dist[i] describes the distance (in kilometers) of the i^th train ride.

Each train can only depart at an integer hour, so you may need to wait in between each train ride.

For example, if the 1^st train ride takes 1.5 hours, you must wait for an additional 0.5 hours before you can depart on the 2^nd train ride at the 2 hour mark.

Return the minimum positive integer speed (in kilometers per hour) that all the trains must travel at for you to reach the office on time, or -1 if it is impossible to be on time.

Tests are generated such that the answer will not exceed 10⁷ and hour will have at most two digits after the decimal point.

Example 1:

Input: dist = [1,3,2], hour = 6 Output: 1 Explanation: At speed 1: - The first train ride takes 1/1 = 1 hour. - Since we are already at an integer hour, we depart immediately at the 1 hour mark. The second train takes 3/1 = 3 hours. - Since we are already at an integer hour, we depart immediately at the 4 hour mark. The third train takes 2/1 = 2 hours. - You will arrive at exactly the 6 hour mark.

Example 2:

Input: dist = [1,3,2], hour = 2.7 Output: 3 Explanation: At speed 3: - The first train ride takes 1/3 = 0.33333 hours. - Since we are not at an integer hour, we wait until the 1 hour mark to depart. The second train ride takes 3/3 = 1 hour. - Since we are already at an integer hour, we depart immediately at the 2 hour mark. The third train takes 2/3 = 0.66667 hours. - You will arrive at the 2.66667 hour mark.

Example 3:

Input: dist = [1,3,2], hour = 1.9 Output: -1 Explanation: It is impossible because the earliest the third train can depart is at the 2 hour mark.

2. Min Speed On Time – Solution

The following is a solution which demonstrates how to find the minimum speed to arrive on time.





		
		
			2. Min Speed On Time - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Sep 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum speed to arrive on time
// ============================================================================
public class Solution {
    public int MinSpeedOnTime(int[] dist, double hour) {
        int left = 1;
        int right = 10000000;
        int minSpeed = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Move to the left half.
            if (TimeRequired(dist, mid) <= hour) {
                minSpeed = mid;
                right = mid - 1;
            } else {
                // Move to the right half.
                left = mid + 1;
            }
        }
        return minSpeed;
    }

    double TimeRequired(int[] dist, int speed) {
        double time = 0.0;
        for (int i = 0 ; i < dist.Length; i++) {
            double t = (double) dist[i] / (double) speed;
            // Round off to the next integer, if not the last ride.
            time += (i == dist.Length - 1 ? t : Math.Ceiling(t));
        }
        return time;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Sep 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum speed to arrive on time
// ============================================================================
public class Solution {
    public int MinSpeedOnTime(int[] dist, double hour) {
        int left = 1;
        int right = 10000000;
        int minSpeed = -1;
 
        while (left <= right) {
            int mid = left + (right - left) / 2;
 
            // Move to the left half.
            if (TimeRequired(dist, mid) <= hour) {
                minSpeed = mid;
                right = mid - 1;
            } else {
                // Move to the right half.
                left = mid + 1;
            }
        }
        return minSpeed;
    }
 
    double TimeRequired(int[] dist, int speed) {
        double time = 0.0;
        for (int i = 0 ; i < dist.Length; i++) {
            double t = (double) dist[i] / (double) speed;
            // Round off to the next integer, if not the last ride.
            time += (i == dist.Length - 1 ? t : Math.Ceiling(t));
        }
        return time;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

1 3 -1

C# || How To Find The Maximum Profit In Job Scheduling Using C#

January 01, 2023 admin No comments

The following is a module with functions which demonstrates how to find the maximum profit in job scheduling using C#.

1. Job Scheduling – Problem Statement

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i].

You’re given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.

If you choose a job that ends at time X you will be able to start another job that starts at time X.

Example 1:

Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] Output: 120 Explanation: The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70.

Example 2:

Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] Output: 150 Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60.

Example 3:

Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6

2. Job Scheduling – Solution

The following is a solution which demonstrates how to find the maximum profit in job scheduling.





		
		
			2. Job Scheduling - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum profit in job scheduling
// ============================================================================
public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        if (startTime == null || startTime.Length == 0) {
            return 0;
        }

        var jobs = new List<Job>();
        for (int index = 0; index < startTime.Length; ++index) {
            jobs.Add(new Job(startTime[index], endTime[index], profit[index]));
        }

        jobs.Sort((a, b) => a.Start - b.Start);

        return DFS(jobs, 0, new Dictionary<int, int>());
    }

    private int DFS(List<Job> jobs, int currentJobIndex, Dictionary<int, int> maxProfits) {
        if (currentJobIndex >= jobs.Count) {
            return 0;
        }

        if (maxProfits.ContainsKey(currentJobIndex)) {
            return maxProfits[currentJobIndex];
        }

        int next = BinarySearch(jobs, currentJobIndex);
        int inc = jobs[currentJobIndex].Profit + (next == -1 ? 0 : DFS(jobs, next, maxProfits));
        int exc = DFS(jobs, currentJobIndex + 1, maxProfits);

        int maxProfit = Math.Max(inc, exc);
        maxProfits[currentJobIndex] =  maxProfit;
        return maxProfit;
    }

    private int BinarySearch(List<Job> jobs, int currentJobIndex) {
        int lo = currentJobIndex;
        int high = jobs.Count - 1;
        int result = -1;

        while (lo <= high) {
            int mid = lo + (high - lo) / 2;

            if (jobs[currentJobIndex].End <= jobs[mid].Start) {
                result = mid;
                high = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return result;
    }

    class Job {
        public int Start { get; set; }
        public int End { get; set; }
        public int Profit { get; set; }

        public Job(int startTime, int endTime, int profit) {
            Start = startTime;
            End = endTime;
            Profit = profit;
        }
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Jan 1, 2023
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find maximum profit in job scheduling
// ============================================================================
public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        if (startTime == null || startTime.Length == 0) {
            return 0;
        }
 
        var jobs = new List<Job>();
        for (int index = 0; index < startTime.Length; ++index) {
            jobs.Add(new Job(startTime[index], endTime[index], profit[index]));
        }
 
        jobs.Sort((a, b) => a.Start - b.Start);
 
        return DFS(jobs, 0, new Dictionary<int, int>());
    }
 
    private int DFS(List<Job> jobs, int currentJobIndex, Dictionary<int, int> maxProfits) {
        if (currentJobIndex >= jobs.Count) {
            return 0;
        }
 
        if (maxProfits.ContainsKey(currentJobIndex)) {
            return maxProfits[currentJobIndex];
        }
 
        int next = BinarySearch(jobs, currentJobIndex);
        int inc = jobs[currentJobIndex].Profit + (next == -1 ? 0 : DFS(jobs, next, maxProfits));
        int exc = DFS(jobs, currentJobIndex + 1, maxProfits);
 
        int maxProfit = Math.Max(inc, exc);
        maxProfits[currentJobIndex] =  maxProfit;
        return maxProfit;
    }
 
    private int BinarySearch(List<Job> jobs, int currentJobIndex) {
        int lo = currentJobIndex;
        int high = jobs.Count - 1;
        int result = -1;
 
        while (lo <= high) {
            int mid = lo + (high - lo) / 2;
 
            if (jobs[currentJobIndex].End <= jobs[mid].Start) {
                result = mid;
                high = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return result;
    }
 
    class Job {
        public int Start { get; set; }
        public int End { get; set; }
        public int Profit { get; set; }
 
        public Job(int startTime, int endTime, int profit) {
            Start = startTime;
            End = endTime;
            Profit = profit;
        }
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

120 150 6

C# || How To Design A Time Based Key-Value Store To Retrieve Timestamps Using C#

November 01, 2022 admin No comments

The following is a module with functions which demonstrates how to design a time based key-value store to retrieve timestamps using C#.

1. Time Map – Problem Statement

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 1:

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"

2. Time Map – Solution

The following is a solution which demonstrates how to design a time based key-value store to retrieve timestamps.





		
		
			2. Time Map - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a time map
// ============================================================================
/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.Set(key,value,timestamp);
 * string param_2 = obj.Get(key,timestamp);
 */
public class TimeMap {
    private class Data {
        public string value;
        public int timestamp;
        public Data(string value, int timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }

    private Dictionary<string, List<Data>> map;

    public TimeMap() {
        map = new Dictionary<string, List<Data>>();
    }

    public void Set(string key, string value, int timestamp) {
        if (!map.ContainsKey(key)) {
            map.Add(key, new List<Data>());
        }
        map[key].Add(new Data(value, timestamp));
    }

    public string Get(string key, int timestamp) {
        if (!map.ContainsKey(key)) {
             return "";
        }
        return BinarySearch(map[key], timestamp);
    }
    
    string BinarySearch(List<Data> bucket, int target) {
        int low = 0, high = bucket.Count;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (bucket[mid].timestamp <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (high == 0) {
            return "";
        }
        return (bucket[high - 1].timestamp <= target) ? bucket[high - 1].value : "";
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 1, 2022
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to design a time map
// ============================================================================
/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.Set(key,value,timestamp);
 * string param_2 = obj.Get(key,timestamp);
 */
public class TimeMap {
    private class Data {
        public string value;
        public int timestamp;
        public Data(string value, int timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }
    }
 
    private Dictionary<string, List<Data>> map;
 
    public TimeMap() {
        map = new Dictionary<string, List<Data>>();
    }
 
    public void Set(string key, string value, int timestamp) {
        if (!map.ContainsKey(key)) {
            map.Add(key, new List<Data>());
        }
        map[key].Add(new Data(value, timestamp));
    }
 
    public string Get(string key, int timestamp) {
        if (!map.ContainsKey(key)) {
             return "";
        }
        return BinarySearch(map[key], timestamp);
    }
    
    string BinarySearch(List<Data> bucket, int target) {
        int low = 0, high = bucket.Count;
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (bucket[mid].timestamp <= target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (high == 0) {
            return "";
        }
        return (bucket[high - 1].timestamp <= target) ? bucket[high - 1].value : "";
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[null,null,"bar","bar",null,"bar2","bar2"]

C# || How To Search In Rotated Sorted Array Using C#

November 26, 2021 admin No comments

The following is a module with functions which demonstrates how to search for a target value in a rotated sorted array using C#.

1. Search – Problem Statement

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1], target = 0 Output: -1

2. Search – Solution

The following is a solution which demonstrates how to search for a target value in a rotated sorted array.

The idea of this solution is to use binary search, and for each loop iteration we compare the midpoint element with the right side of the array to determine the search area of where the target element might be.





		
		
			2. Search - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 26, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to search for a target in a rotated array
// ============================================================================
public class Solution {
    public int Search(int[] nums, int target) {
        var lo = 0;
        var hi = nums.Length - 1;

        while (lo <= hi) {
            var mid = lo + (hi - lo) / 2;

            // Target element found
            if (nums[mid] == target) {
                return mid;

            // Midpoint element is greater than right side of array
            } else if (nums[mid] > nums[hi]) {
                // Determine which side of array to adjust
                if (target < nums[mid] && target >= nums[lo]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }

            // Midpoint element is less than right side of array
            } else {
                // Determine which side of array to adjust
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 26, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to search for a target in a rotated array
// ============================================================================
public class Solution {
    public int Search(int[] nums, int target) {
        var lo = 0;
        var hi = nums.Length - 1;
 
        while (lo <= hi) {
            var mid = lo + (hi - lo) / 2;
 
            // Target element found
            if (nums[mid] == target) {
                return mid;
 
            // Midpoint element is greater than right side of array
            } else if (nums[mid] > nums[hi]) {
                // Determine which side of array to adjust
                if (target < nums[mid] && target >= nums[lo]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
 
            // Midpoint element is less than right side of array
            } else {
                // Determine which side of array to adjust
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

4 -1 -1

C# || How To Find Single Element In A Sorted Array Using C#

November 19, 2021 admin No comments

The following is a module with functions which demonstrates how to find a single element in a sorted array using C#.

1. Single Non Duplicate – Problem Statement

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

Your solution must run in O(log n) time and O(1) space.

Example 1:

Input: nums = [1,1,2,3,3,4,4,8,8] Output: 2

Example 2:

Input: nums = [3,3,7,7,10,11,11] Output: 10

2. Single Non Duplicate – Solution

The following is a solution which demonstrates how to find a single element in a sorted array.

The idea of this solution is the following:

Suppose we have the following array: [1,1,2,2,3,3,4,4,6,8,8]

We can observe that for each pair:

The first pair element takes the even array index position The second pair element takes the odd array index position

For example, when examining the number 1 as a pair, we see it takes the array index positions 0 and 1.

Similarly for all other pairs, the first pair element takes the even array index position, and the second pair element takes the odd array index position.

Using this idea, we can see that this pattern for pairs will break when a single element appears in the array.

In this solution, we use binary search to look for the point in the array where the pattern mentioned above for the pairs first breaks





		
		
			2. Single Non Duplicate - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 19, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find a single element in a sorted array
// ============================================================================
public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        var lo = 0;
        var hi = nums.Length - 1;

        while (lo < hi) {
            // Get the mipoint
            var mid = lo + (hi - lo) / 2;

            // Check to see if mid is even
            var isEven = mid % 2 == 0;

            // If mid is even, its duplicate should be the next index
            // If mid is odd, its duplicate should be the previous index
            if ((isEven && nums[mid] == nums[mid + 1]) || (!isEven && nums[mid] == nums[mid - 1])) {
                // Duplicate found, advance to next index. Single element is > mid
                lo = mid + 1;
            } else {
                // Pattern is broken. Single element is <= mid
                hi = mid;
            }
        }
        return nums[lo];
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 19, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find a single element in a sorted array
// ============================================================================
public class Solution {
    public int SingleNonDuplicate(int[] nums) {
        var lo = 0;
        var hi = nums.Length - 1;
 
        while (lo < hi) {
            // Get the mipoint
            var mid = lo + (hi - lo) / 2;
 
            // Check to see if mid is even
            var isEven = mid % 2 == 0;
 
            // If mid is even, its duplicate should be the next index
            // If mid is odd, its duplicate should be the previous index
            if ((isEven && nums[mid] == nums[mid + 1]) || (!isEven && nums[mid] == nums[mid - 1])) {
                // Duplicate found, advance to next index. Single element is > mid
                lo = mid + 1;
            } else {
                // Pattern is broken. Single element is <= mid
                hi = mid;
            }
        }
        return nums[lo];
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

2 10

C# || How To Find Friends Of Appropriate Ages Using C#

November 05, 2021 admin No comments

The following is a module with functions which demonstrates how to find friends of appropriate ages using C#.

1. Num Friend Requests – Problem Statement

There are n persons on a social media website. You are given an integer array ages where ages[i] is the age of the i^th person.

A Person x will not send a friend request to a person y (x != y) if any of the following conditions is true:

age[y] <= 0.5 * age[x] + 7
age[y] > age[x]
age[y] > 100 && age[x] < 100

Otherwise, x will send a friend request to y.

Note that if x sends a request to y, y will not necessarily send a request to x. Also, a person will not send a friend request to themself.

Return the total number of friend requests made.

Example 1:

Input: ages = [16,16] Output: 2 Explanation: 2 people friend request each other.

Example 2:

Input: ages = [16,17,18] Output: 2 Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: ages = [20,30,100,110,120] Output: 3 Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

2. Num Friend Requests – Solution

The following is a solution which demonstrates how to find friends of appropriate ages.

In this solution, we sort the ages and use a map that keeps track of the ages, and the total friend request count that age can recieve.

Binary search is used to get the age range in the array that satisfies the friend request conditions for a given age.





		
		
			2. Num Friend Requests - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 5, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find friends of appropriate ages
// ============================================================================
public class Solution {
    public int NumFriendRequests(int[] ages) {
        var result = 0;

        // Sort ages
        Array.Sort(ages);

        // Keep track of results calculated
        var seen = new Dictionary<int, int>();

        // Iterate array backwards
        for (int index = ages.Length - 1; index >= 0; --index) {
            // Check if we already calculated result for age
            if (!seen.ContainsKey(ages[index])) {
                // Binary search
                var lo = 0;
                var hi = index;
                while (lo < hi) {
                    var mid = lo + (hi - lo) / 2;

                    // Check if friends can be made in this range
                    if (!CanFriend(ages[index], ages[mid])) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                // Get distance between index and hi. This is the friend count for the age
                seen[ages[index]] = index - hi;
            }
            // Update result count
            result += seen[ages[index]];
        }

        return result;
    }

    private bool CanFriend(int x, int y) {
        return !((y > x) || (y > 100 && x < 100) || (y <= 0.5 * x + 7));
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 5, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find friends of appropriate ages
// ============================================================================
public class Solution {
    public int NumFriendRequests(int[] ages) {
        var result = 0;
 
        // Sort ages
        Array.Sort(ages);
 
        // Keep track of results calculated
        var seen = new Dictionary<int, int>();
 
        // Iterate array backwards
        for (int index = ages.Length - 1; index >= 0; --index) {
            // Check if we already calculated result for age
            if (!seen.ContainsKey(ages[index])) {
                // Binary search
                var lo = 0;
                var hi = index;
                while (lo < hi) {
                    var mid = lo + (hi - lo) / 2;
 
                    // Check if friends can be made in this range
                    if (!CanFriend(ages[index], ages[mid])) {
                        lo = mid + 1;
                    } else {
                        hi = mid;
                    }
                }
                // Get distance between index and hi. This is the friend count for the age
                seen[ages[index]] = index - hi;
            }
            // Update result count
            result += seen[ages[index]];
        }
 
        return result;
    }
 
    private bool CanFriend(int x, int y) {
        return !((y > x) || (y > 100 && x < 100) || (y <= 0.5 * x + 7));
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

2 2 3

C# || How To Traverse Binary Tree Zigzag Level Order Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to traverse binary tree zigzag level order using C#.

1. Zigzag Level Order – Problem Statement

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

2. Zigzag Level Order – Solution

The following is a solution which demonstrates how to traverse binary tree zigzag level order.

This solution uses Breadth First Search to explore items at each level.





		
		
			2. Zigzag Level Order - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a tree zigzag level order
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var stack = new Stack<TreeNode>();

        // Add root to stack
        if (root != null) {
            stack.Push(root);
        }

        var leftToRight = true;
        while (stack.Count > 0) {
            var queue = new Queue<TreeNode>();
            var level = new List<int>();

            // Add items at the top of the stack to the current level
            for (var itemCount = stack.Count; itemCount > 0; --itemCount) {
                var current = stack.Peek();
                stack.Pop();

                level.Add(current.val);
                queue.Enqueue(current);
            }

            // Add level to result
            result.Add(level);

            // Go through items in the queue and add them to the stack in the proper order
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();

                // Add children to the stack
                // Left to right or Right to left order
                if (leftToRight) {
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                } else {
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                }
            }
            // Alternate order for the next level
            leftToRight = !leftToRight;
        }
        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 29, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to traverse a tree zigzag level order
// ============================================================================
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
        var stack = new Stack<TreeNode>();
 
        // Add root to stack
        if (root != null) {
            stack.Push(root);
        }
 
        var leftToRight = true;
        while (stack.Count > 0) {
            var queue = new Queue<TreeNode>();
            var level = new List<int>();
 
            // Add items at the top of the stack to the current level
            for (var itemCount = stack.Count; itemCount > 0; --itemCount) {
                var current = stack.Peek();
                stack.Pop();
 
                level.Add(current.val);
                queue.Enqueue(current);
            }
 
            // Add level to result
            result.Add(level);
 
            // Go through items in the queue and add them to the stack in the proper order
            for (var itemCount = queue.Count; itemCount > 0; --itemCount) {
                var current = queue.Peek();
                queue.Dequeue();
 
                // Add children to the stack
                // Left to right or Right to left order
                if (leftToRight) {
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                } else {
                    if (current.right != null) {
                        stack.Push(current.right);
                    }
                    if (current.left != null) {
                        stack.Push(current.left);
                    }
                }
            }
            // Alternate order for the next level
            leftToRight = !leftToRight;
        }
        return result;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[[3],[20,9],[15,7]] [[1]] []

C# || How To Find Longest Duplicate Substring Using C#

October 30, 2021 admin No comments

The following is a module with functions which demonstrates how to find the longest duplicate substring using C#.

1. Longest Dup Substring – Problem Statement

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is “”.

Example 1:

Input: s = "banana" Output: "ana"

Example 2:

Input: s = "abcd" Output: ""

2. Longest Dup Substring – Solution

The following is a solution which demonstrates how find the longest duplicate substring.

This solution uses Binary Search and Rolling Hash.





		
		
			2. Longest Dup Substring - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the longest duplicate substring
// ============================================================================
public class Solution {
    public string LongestDupSubstring(string s) {
        // Convert string to array of ascii integers
        // to implement constant time slice
        var nums = new int[s.Length];
        for (int index = 0; index < s.Length; ++index) {
            nums[index] = (int)s[index] - (int)'a';
        }

        // Keeps track of substring start index and length
        var startIndex = -1;
        var substrLength = -1;

        // Use binary search to find the largest possible length of a duplicate substring
        var left = 1;
        var right = s.Length;
        while (left < right) {
            var mid = left + (right - left) / 2;

            // Rolling hash (Rabin-Karp)
            var index = RollingSearch(nums, mid);

            // Substring found
            if (index != -1) {
                if (mid > substrLength) {
                    startIndex = index;
                    substrLength = mid;
                }
                left = mid + 1;

            // Substring not found
            } else {
               right = mid;
            }
        }
        return substrLength != -1 ? s.Substring(startIndex, substrLength): "";
    }

    private int RollingSearch(int[] nums, int mid) {
        var seen = new HashSet<long>();

        // Base value for the rolling hash function
        var a = 31;

        // Current hash
        var hash = Hash(nums, mid, a);

        seen.Add(hash);

        long pow = 1;
        for (var index = 1; index < mid; ++index) {
            pow *= a;
        }

        var result = -1;
        for (var index = 1; index < nums.Length - mid + 1; ++index) {
            // Compute rolling hash
            hash = RollingHash(pow, hash, nums[index - 1], nums[index + mid - 1], a);

            // Hash found
            if (seen.Contains(hash)) {
                result = index;
                break;
            }
            // Hash not found
            seen.Add(hash);
        }
        return result;
    }

    private long Hash(int[] nums, int mid, int a) {
        long h = 0;
        long aL = 1;
        for (var index = mid; index >= 1; --index) {
            h += (nums[index - 1] + 1) * aL;
            aL *= a;
        }
        return h;
    }

    private long RollingHash(long pow, long hash, int left, int right, int a) {
        return (hash - (left + 1) * pow) * a + (right + 1);
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 30, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the longest duplicate substring
// ============================================================================
public class Solution {
    public string LongestDupSubstring(string s) {
        // Convert string to array of ascii integers
        // to implement constant time slice
        var nums = new int[s.Length];
        for (int index = 0; index < s.Length; ++index) {
            nums[index] = (int)s[index] - (int)'a';
        }
 
        // Keeps track of substring start index and length
        var startIndex = -1;
        var substrLength = -1;
 
        // Use binary search to find the largest possible length of a duplicate substring
        var left = 1;
        var right = s.Length;
        while (left < right) {
            var mid = left + (right - left) / 2;
 
            // Rolling hash (Rabin-Karp)
            var index = RollingSearch(nums, mid);
 
            // Substring found
            if (index != -1) {
                if (mid > substrLength) {
                    startIndex = index;
                    substrLength = mid;
                }
                left = mid + 1;
 
            // Substring not found
            } else {
               right = mid;
            }
        }
        return substrLength != -1 ? s.Substring(startIndex, substrLength): "";
    }
 
    private int RollingSearch(int[] nums, int mid) {
        var seen = new HashSet<long>();
 
        // Base value for the rolling hash function
        var a = 31;
 
        // Current hash
        var hash = Hash(nums, mid, a);
 
        seen.Add(hash);
 
        long pow = 1;
        for (var index = 1; index < mid; ++index) {
            pow *= a;
        }
 
        var result = -1;
        for (var index = 1; index < nums.Length - mid + 1; ++index) {
            // Compute rolling hash
            hash = RollingHash(pow, hash, nums[index - 1], nums[index + mid - 1], a);
 
            // Hash found
            if (seen.Contains(hash)) {
                result = index;
                break;
            }
            // Hash not found
            seen.Add(hash);
        }
        return result;
    }
 
    private long Hash(int[] nums, int mid, int a) {
        long h = 0;
        long aL = 1;
        for (var index = mid; index >= 1; --index) {
            h += (nums[index - 1] + 1) * aL;
            aL *= a;
        }
        return h;
    }
 
    private long RollingHash(long pow, long hash, int left, int right, int a) {
        return (hash - (left + 1) * pow) * a + (right + 1);
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

"ana" ""

C# || Two Sum II – How To Get Two Numbers In Sorted Array Equal To Target Value Using C#

October 28, 2021 admin No comments

The following is a module with functions which demonstrates how to get two numbers in a sorted array equal to target value using C#.

1. Two Sum II – Problem Statement

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index₁] and numbers[index₂] where 1 <= index₁ < index₂ <= numbers.length.

Return the indices of the two numbers, index₁ and index₂, added by one as an integer array [index₁, index₂] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Example 1:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

2. Two Sum II – Solution

The following is a solution which demonstrates how to get two numbers in sorted array equal to target value.

In this solution, Binary Search is used to find the two numbers.





		
		
			2. Two Sum II - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        var result = new int[2];

        var lo = 0;
        var hi = numbers.Length - 1;

        while (lo < hi) {
            var m = lo + (hi - lo) / 2;
            var sum = numbers[lo] + numbers[hi];

            if (sum == target) {
                result[0] = lo + 1;
                result[1] = hi + 1;
                break;
            } else if (sum < target) {
                // Determine if mid is less than the remaining value
                // Increase lo to equal mid if so
                if (numbers[m] < target - numbers[hi]) {
                    lo = m + 1;
                } else {
                    lo = lo + 1;
                }
            } else {
                // Determine if mid is greater than the remaining value
                // Decrease hi to equal mid if so
                if (numbers[m] > target - numbers[lo]) {
                    hi = m - 1;
                } else {
                    hi = hi - 1;
                }
            }
        }

        return result;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 28, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to get two numbers equal to target value
// ============================================================================
public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        var result = new int[2];
 
        var lo = 0;
        var hi = numbers.Length - 1;
 
        while (lo < hi) {
            var m = lo + (hi - lo) / 2;
            var sum = numbers[lo] + numbers[hi];
 
            if (sum == target) {
                result[0] = lo + 1;
                result[1] = hi + 1;
                break;
            } else if (sum < target) {
                // Determine if mid is less than the remaining value
                // Increase lo to equal mid if so
                if (numbers[m] < target - numbers[hi]) {
                    lo = m + 1;
                } else {
                    lo = lo + 1;
                }
            } else {
                // Determine if mid is greater than the remaining value
                // Decrease hi to equal mid if so
                if (numbers[m] > target - numbers[lo]) {
                    hi = m - 1;
                } else {
                    hi = hi - 1;
                }
            }
        }
 
        return result;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[1,2] [1,3] [1,2]

C# || How To Find Minimum In Rotated Sorted Array With Duplicates Using C#

October 22, 2021 admin No comments

The following is a module with functions which demonstrates how to find the minimum value in a rotated sorted array with duplicates using C#.

1. Find Min Duplicates – Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

[4,5,6,7,0,1,4] if it was rotated 4 times.
[0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [1,3,5] Output: 1

Example 2:

Input: nums = [2,2,2,0,1] Output: 0

2. Find Min Duplicates – Solution

The following is a solution which demonstrates how to find the minimum value in a rotated sorted array with duplicates.





		
		
			2. Find Min Duplicates - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 22, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum value in a sorted array
// ============================================================================
public class Solution {
    public int FindMin(int[] nums) {
        var lo = 0;
        var hi = nums.Length - 1;

        // In cases where the front and back of the array are the
        // same (ex: [1,19,28,87,91,0,1,1,1]), decrease the end of the array
        while (nums[lo] == nums[hi] && lo < hi) {
            --hi;
        }

        // Perform binary search
        while (lo < hi) {
            var mid = lo + (hi - lo) / 2;

            // Midpoint element is greater than right side of array, so
            // the minumum element is somewhere on the right side of array.
            // Advance lo value to equal midpoint + 1
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;

            // Midpoint element is less than right side of array, so
            // the minumum element is somewhere on the left side of array.
            // Decrease hi value to equal midpoint
            } else if (nums[mid] < nums[hi]) {
                hi = mid;

            // Duplicate element found (nums[mid] == nums[hi])
            } else {
                --hi;
            }
        }

        return nums[lo];
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 22, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum value in a sorted array
// ============================================================================
public class Solution {
    public int FindMin(int[] nums) {
        var lo = 0;
        var hi = nums.Length - 1;
 
        // In cases where the front and back of the array are the
        // same (ex: [1,19,28,87,91,0,1,1,1]), decrease the end of the array
        while (nums[lo] == nums[hi] && lo < hi) {
            --hi;
        }
 
        // Perform binary search
        while (lo < hi) {
            var mid = lo + (hi - lo) / 2;
 
            // Midpoint element is greater than right side of array, so
            // the minumum element is somewhere on the right side of array.
            // Advance lo value to equal midpoint + 1
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;
 
            // Midpoint element is less than right side of array, so
            // the minumum element is somewhere on the left side of array.
            // Decrease hi value to equal midpoint
            } else if (nums[mid] < nums[hi]) {
                hi = mid;
 
            // Duplicate element found (nums[mid] == nums[hi])
            } else {
                --hi;
            }
        }
 
        return nums[lo];
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

1 0

C# || How To Find Minimum In Rotated Sorted Array Using C#

October 22, 2021 admin No comments

The following is a module with functions which demonstrates how to find the minimum value in a rotated sorted array using C#.

1. Find Min – Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n) time.

Example 1:

Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

2. Find Min – Solution

The following is a solution which demonstrates how to find the minimum value in a rotated sorted array.





		
		
			2. Find Min - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 22, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum value in a sorted array
// ============================================================================
public class Solution {
    public int FindMin(int[] nums) {
        var lo = 0;
        var hi = nums.Length - 1;

        while (lo < hi) {
            var mid = lo + (hi - lo) / 2;

            // Midpoint element is greater than right side of array, so
            // the minumum element is somewhere on the right side of array.
            // Advance lo value to equal midpoint + 1
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;

            // Midpoint element is less than right side of array, so
            // the minumum element is somewhere on the left side of array.
            // Decrease hi value to equal midpoint
            } else if (nums[mid] < nums[hi]) {
                hi = mid;

            // Minimum element found
            } else {
                lo = mid;
                break;
            }
        }

        return nums[lo];
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Oct 22, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find the minimum value in a sorted array
// ============================================================================
public class Solution {
    public int FindMin(int[] nums) {
        var lo = 0;
        var hi = nums.Length - 1;
 
        while (lo < hi) {
            var mid = lo + (hi - lo) / 2;
 
            // Midpoint element is greater than right side of array, so
            // the minumum element is somewhere on the right side of array.
            // Advance lo value to equal midpoint + 1
            if (nums[mid] > nums[hi]) {
                lo = mid + 1;
 
            // Midpoint element is less than right side of array, so
            // the minumum element is somewhere on the left side of array.
            // Decrease hi value to equal midpoint
            } else if (nums[mid] < nums[hi]) {
                hi = mid;
 
            // Minimum element found
            } else {
                lo = mid;
                break;
            }
        }
 
        return nums[lo];
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

1 0 11

Tag Archives: binary search

C# || How To Find The Minimum Speed To Arrive On Time Using C#

C# || How To Find The Maximum Profit In Job Scheduling Using C#

C# || How To Design A Time Based Key-Value Store To Retrieve Timestamps Using C#

C# || How To Search In Rotated Sorted Array Using C#

C# || How To Find Single Element In A Sorted Array Using C#

C# || How To Find Friends Of Appropriate Ages Using C#

C# || How To Traverse Binary Tree Zigzag Level Order Using C#

C# || How To Find Longest Duplicate Substring Using C#

C# || Two Sum II – How To Get Two Numbers In Sorted Array Equal To Target Value Using C#

C# || How To Find Minimum In Rotated Sorted Array With Duplicates Using C#

C# || How To Find Minimum In Rotated Sorted Array Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories