Skip to content

Commit 8a9b73d

Browse files
paramagparamag
paramag
authored and
paramag
committed
Median of 2 sorted array and lexicographic order problems.
1 parent 4407796 commit 8a9b73d

6 files changed

Lines changed: 161 additions & 2 deletions

File tree

‎Algorithm/.vs/Algorithms/v14/.suo‎

8 KB
Binary file not shown.

‎Algorithm/LeetCode/Algorithms.Problems.LeetCode.csproj‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -47,6 +47,7 @@
4747
<Compile Include="Arrays\AddTwoNumbersProblem.cs" />
4848
<Compile Include="Arrays\ClockSum.cs" />
4949
<Compile Include="Arrays\LengthOfLongestSubStringProblem.cs" />
50+
<Compile Include="Arrays\MedianOfArray.cs" />
5051
<Compile Include="Arrays\SearchInArrays.cs" />
5152
<Compile Include="Arrays\TwoSumProblem.cs" />
5253
<Compile Include="LinkedList\ListNode.cs" />
@@ -59,6 +60,7 @@
5960
<Compile Include="PlayGround.cs" />
6061
<Compile Include="Properties\AssemblyInfo.cs" />
6162
<Compile Include="String\PhoneLetterCombinationLexicographical.cs" />
63+
<Compile Include="String\LexicographicOrder.cs" />
6264
<Compile Include="String\ZigZagDisplayCharacters.cs" />
6365
</ItemGroup>
6466
<ItemGroup>

‎Algorithm/LeetCode/Arrays/MedianOfArray.cs‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
using Microsoft.VisualStudio.TestTools.UnitTesting;
2+
using System;
3+
using System.Collections.Generic;
4+
using System.Linq;
5+
using System.Text;
6+
using System.Threading.Tasks;
7+
8+
namespace LeetCode.Arrays
9+
{
10+
[TestClass]
11+
public class MedianOfArray
12+
{
13+
public int MedianOfTwoSortedArray(int[] a1, int[] a2, int start, int end)
14+
{
15+
int median = -1;
16+
17+
while(start < end)
18+
{
19+
// find the median such that length of left elements and right elements are same.
20+
// identify the median of a1
21+
int partitionA1 = end + start / 2;
22+
int partitionA2 = ((a1.Length + a2.Length + 1) / 2) - partitionA1;
23+
24+
int leftPartitionA1 = a1[partitionA1 - 1];
25+
int leftPartitionA2 = a2[partitionA2 - 1];
26+
int rightPartitionA1 = a1[partitionA1];
27+
int rightPartitionA2 = a2[partitionA2];
28+
29+
if (a1[leftPartitionA1] <= a2[rightPartitionA2] &&
30+
a2[leftPartitionA2] <= a1[rightPartitionA1])
31+
{
32+
// the median is found
33+
// if the elements are odd then it will be max(a1[leftPartitionA1] , a2[leftPartitionA2] )
34+
// if the elements are even then it will be Avg(max(a1[leftPartitionA1], a2[leftPartitionA2]) , min(a1[rightPartitionA1], a2[rightPartitionA2])
35+
if (a1.Length + a2.Length % 2 == 0)
36+
{
37+
median = (Math.Max(a1[leftPartitionA1], a2[leftPartitionA2])
38+
+ Math.Min(a1[rightPartitionA1], a2[rightPartitionA2])) / 2;
39+
}
40+
else
41+
{
42+
median = Math.Max(a1[leftPartitionA1], a2[leftPartitionA2]);
43+
}
44+
}
45+
else if (a1[leftPartitionA1] >= a2[rightPartitionA2])
46+
{
47+
// move towards left.
48+
end = partitionA1 - 1;
49+
}
50+
else
51+
{
52+
start = partitionA1;
53+
}
54+
}
55+
56+
return median;
57+
}
58+
59+
[TestMethod]
60+
public void TestMethod()
61+
{
62+
int[] sortedArrayA1 = new[] { 1, 3, 8, 9, 15 };
63+
int[] sortedArrayA2 = new[] { 7, 11, 18, 19, 21, 25 };
64+
65+
this.MedianOfTwoSortedArray(sortedArrayA1, sortedArrayA2, 0, sortedArrayA1.Length);
66+
}
67+
}
68+
}

‎Algorithm/LeetCode/Matrix/WordSearchProblem.cs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -82,8 +82,8 @@ public bool WordSearchZigZagHelper(char[,] matrix, string word, int row, int col
8282
int cold = col + colDir[i];
8383

8484
if (!(rowd < 0 || cold < 0 || rowd >= matrix.GetLength(0) || cold >= matrix.GetLength(1)) // check for boundaries.
85-
&& matrix[rowd, cold] == word[wordCount]
86-
&& !visitedArray[rowd, cold])
85+
&& matrix[rowd, cold] == word[wordCount] // check for char that matches
86+
&& !visitedArray[rowd, cold]) // check if it's already visited previously.
8787
{
8888
return this.WordSearchZigZagHelper(matrix, word, rowd, cold, visitedArray, wordCount + 1, wordStr + matrix[rowd, cold]);
8989
}

‎Algorithm/LeetCode/String/LexicographicOrder.cs‎

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
using Microsoft.VisualStudio.TestTools.UnitTesting;
2+
using System;
3+
using System.Collections.Generic;
4+
using System.Linq;
5+
using System.Text;
6+
using System.Threading.Tasks;
7+
8+
namespace LeetCode.String
9+
{
10+
[TestClass]
11+
public class LexicographicOrder
12+
{
13+
/// <summary>
14+
/// Watch this video for explanation: https://www.youtube.com/watch?v=nYFd7VHKyWQ
15+
/// </summary>
16+
/// <param name="characters"></param>
17+
public List<string> PrintLexicographicOrder(string characters)
18+
{
19+
Dictionary<char, int> characterMap = new Dictionary<char, int>();
20+
foreach(char c in characters)
21+
{
22+
if (characterMap.ContainsKey(c))
23+
{
24+
characterMap[c] += 1;
25+
}
26+
else
27+
{
28+
characterMap[c] = 1;
29+
}
30+
}
31+
var outputOrder = new List<string>();
32+
this.PrintLexicographicOrderHelper(characterMap.Keys.ToArray(), characterMap.Values.ToArray(), new char[characters.Length], 0, outputOrder);
33+
34+
return outputOrder;
35+
}
36+
37+
public void PrintLexicographicOrderHelper(char[] currentCharOutput, int[] charCountArray, char[] resultArray, int level, List<string> result)
38+
{
39+
// if the count is equal to the leng of the character, then print them.
40+
if (level == resultArray.Length)
41+
{
42+
string resultChar = new string(resultArray);
43+
System.Diagnostics.Debug.WriteLine(resultChar);
44+
result.Add(resultChar);
45+
return;
46+
}
47+
48+
for(int i=0; i < currentCharOutput.Length; i++)
49+
{
50+
if (charCountArray[i] == 0)
51+
{
52+
continue;
53+
}
54+
55+
resultArray[level] = currentCharOutput[i];
56+
charCountArray[i]--;
57+
58+
this.PrintLexicographicOrderHelper(currentCharOutput, charCountArray, resultArray, level + 1, result);
59+
60+
charCountArray[i]++;
61+
}
62+
}
63+
64+
[TestMethod]
65+
public void TestMethod()
66+
{
67+
List<string> expectedOutput = new List<string> { "ABC", "ACB", "BAC", "BCA", "CAB", "CBA"};
68+
69+
List <string> actualOutput = this.PrintLexicographicOrder("ABC");
70+
}
71+
}
72+
}

‎Algorithm/LeetCode/String/PhoneLetterCombinationLexicographical.cs‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,22 +15,39 @@ public class PhoneLetterCombinationLexicographical
1515
public IList<string> LetterCombinations(string digits)
1616
{
1717
IList<string> letterCombination = new List<string>();
18+
19+
// if digits = 2
20+
// this.LetterCombinationHelper("23", 2, new char[2], 0, letterCombination);
1821
this.LetterCombinationHelper(digits, digits.Length, new char[digits.Length], 0, letterCombination);
1922

2023
return letterCombination;
2124
}
2225

26+
/// <summary>
27+
/// Letter combination helper for recursive calls.
28+
/// </summary>
29+
/// <param name="digits">The given digits like "23".</param>
30+
/// <param name="len">The length of the digits like "23" which is 2.</param>
31+
/// <param name="output">The output chars to be print for every iteration, like ad, ae, af.</param>
32+
/// <param name="count">The count that tracks the length of digits for every recursion call.</param>
33+
/// <param name="letterCombination">The letter combination result where intermediate results are added.</param>
2334
public void LetterCombinationHelper(string digits, int len, char[] output, int count, IList<string> letterCombination)
2435
{
2536
if (len == count)
2637
{
38+
// store the result, if len is equal to the count.
2739
letterCombination.Add(new string(output));
2840
System.Diagnostics.Debug.WriteLine(new string(output));
2941
return;
3042
}
3143

44+
// gets the index to look up from letterList
45+
// if the digits = "23", then digits[0] = 2, lookup 2nd index from letterList (the phone keypad combination).
3246
int index = int.Parse(digits[count].ToString());
3347

48+
// Loop through the letterList for the digit's index.
49+
// for instance: index:2 then letterList[2] = abc, in the recursion call it will fetch from letterList[3] def,
50+
// if count == 2 then it will print 'ad', 'ae', 'af' before going to next from the index 2 i.e. 'b'
3451
for (int i = 0; i < letterList[index].Length; i++)
3552
{
3653
output[count] = letterList[index][i];

0 commit comments

Comments
 (0)