Daily Archives: October 22, 2021
C# || How To Find Minimum In Rotated Sorted Array With Duplicates Using C#
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.
|
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#
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.
|
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
C# || How To Find Longest Arithmetic Subsequence Of An Array Using C#
The following is a module with functions which demonstrates how to find the longest arithmetic subsequence of an array using C#.
1. Longest Arithmetic Subsequence Length – Problem Statement
Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.
Recall that a subsequence of an array nums is a list nums[i1], nums[i2], …, nums[ik] with 0 <= i1 < i2 < … < ik <= nums.length – 1, and that a sequence seq is arithmetic if seq[i+1] – seq[i] are all the same value (for 0 <= i < seq.length – 1).
Example 1:
Input: nums = [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.
Example 2:
Input: nums = [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].
Example 3:
Input: nums = [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].
2. Longest Arithmetic Subsequence Length – Solution
The following is a solution which demonstrates how to find the longest arithmetic subsequence of an array.
The main idea in this solution is to maintain a dictionary map array of the differences seen at each index, where dp[index][diff] holds the frequency count at that index, for that specific diff.
Each item in the array is considered and checked against to their items to the left.
For each number (i,j) we determine the difference d = nums[i] – nums[j] and keep a count of the frequency the difference has been seen.
In the end, the max difference frequency is returned.
|
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 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 22, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to find longest arithmetic subsequence // ============================================================================ public class Solution { public int LongestArithSeqLength(int[] nums) { var result = 0; // Create a map array of size n var dp = new Dictionary<int, int>[nums.Length]; // Iterate the numbers in the array for (int i = 0; i < nums.Length; ++i) { // Create a new dictionary for this index dp[i] = new Dictionary<int, int>(); // Iterate over values to the left of i for (int j = 0; j < i; ++j) { // Get the difference between the two numbers var currentDiff = nums[i] - nums[j]; // Update the count matching the difference already seen from j for i dp[i][currentDiff] = (dp[j].ContainsKey(currentDiff) ? dp[j][currentDiff] : 0) + 1; // Keep track of the max difference count result = Math.Max(result, dp[i][currentDiff]); } } return result + 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
3
4
Hi, I'm a software engineer. I write articles about programming and design in my spare time.
