Tag Archives: binary search

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

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.

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#

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

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#

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 ith 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.

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#

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:

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.

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#

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.

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#

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[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] 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.

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#

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.

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.

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