Month: August 2020

Posted on

LeetCode: Longest Substring Without Repeating Characters (Solution)

Link to the description of the task: https://leetcode.com/problems/longest-substring-without-repeating-characters/

public class Solution
{
public int LengthOfLongestSubstring(string s)
{
var given = s.ToCharArray();
var charsPositions = new Dictionary<char, int>();
int startPosition = 0, maxLength = 0;
for (var endPosition = 0; endPosition < given.Count(); endPosition++)
{
var ch = given[endPosition];
if (!charsPositions.ContainsKey(ch))
{
charsPositions.Add(ch, endPosition);
maxLength = Math.Max(maxLength, charsPositions.Count);
}
else
{
var prevCharPosition = charsPositions[ch];
foreach (var charToRemove in given[startPosition..prevCharPosition])
{
charsPositions.Remove(charToRemove);
}
charsPositions[ch] = endPosition;
startPosition = prevCharPosition + 1;
}
}
return maxLength;
}
}
view raw solution.cs hosted with ❤ by GitHub
Posted on

LeetCode: The Earliest Moment When Everyone Become Friends (Solution with Time Complexity Analysis)

Link to the description of the task: https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/

Straightforward Solution:

using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
var log = new FrienshipRecord[] {
new FrienshipRecord() { Time = 0, Member1 = "a", Member2 = "b" },
new FrienshipRecord() { Time = 1, Member1 = "c", Member2 = "d" },
new FrienshipRecord() { Time = 2, Member1 = "d", Member2 = "e" },
new FrienshipRecord() { Time = 3, Member1 = "f", Member2 = "e" },
new FrienshipRecord() { Time = 4, Member1 = "a", Member2 = "f" },
new FrienshipRecord() { Time = 5, Member1 = "c", Member2 = "a" },
};
var socialNetwork = new List<List<string>>();
int totalMembersCount = 6;
foreach (var record in log)
{
var group1 = socialNetwork.FirstOrDefault(g => g.Contains(record.Member1)); // O(n)
var group2 = socialNetwork.FirstOrDefault(g => g.Contains(record.Member2)); // O(n)
switch (group1 is null, group2 is null)
{
case (false, false) when group1 == group2:
// do nothing
break;
case (false, false) when group1 != group2:
group1.AddRange(group2); // O(l)
socialNetwork.Remove(group2); // O(1)
break;
case (false, true):
group1.Add(record.Member2); // O(1) or O(k)
break;
case (true, false):
group2.Add(record.Member1); // O(1) or O(k)
break;
case (true, true):
socialNetwork.Add(new List<string>() { record.Member1, record.Member2 }); // O(2)
break;
}
// If the social network contains only one group
// and also the grop contains all the members
if (socialNetwork.Count == 1 && socialNetwork[0].Count == totalMembersCount) // O(1)
{
Console.WriteLine("All members were friends at " + record.Time);
return;
}
}
Console.WriteLine("Not all of the members are friends yet");
}
}
internal struct FrienshipRecord
{
internal int Time;
internal string Member1;
internal string Member2;
}
}
view raw List<List<string>> hosted with ❤ by GitHub

Time Complexity Analysis:

List.Add(newFriend) -> O(1) if Count is less than Capacity, otherwise O(k) where k is Count

List.AddRange(anotherList) -> O(l) if Capacity is less than Count plus l, otherwise O(Count + l) where l is anotherList.Count

List.Contains(member) -> O(k) where k is Count

Loop:

  1. Take a record from the log
  2. Get groups ids for each member {List.Contains(member)} -> 2 * O(n)
  3. If the ids are the same then do nothing
  4. If one of the ids is null then add the member {List.Add(newFriend) -> O(1) or O(k)
  5. If both are null then create new Group {new List{a, b}} -> O(2)
  6. If not null and different then merge groups {List.AddRange} -> O(l)
  7. If the base List.Count is 1 and List[0].Count equals n then the current record is the answer

The total complexity is m * O(n). Also, m must be equal or larger then log(n) to make all members connected. This way the solution complexity is at least O(log(n) * n)

Two problems with this method:

  1. Getting a group id for a member is too slow (O(n))
  2. Merging groups is slow (O(n)) in the worst-case scenario

Straightforward Solution with HashSet:

using System;
using System.Collections.Generic;
using System.Linq;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
var log = new FrienshipRecord[] {
new FrienshipRecord() { Time = 0, Member1 = "a", Member2 = "b" },
new FrienshipRecord() { Time = 1, Member1 = "c", Member2 = "d" },
new FrienshipRecord() { Time = 2, Member1 = "d", Member2 = "e" },
new FrienshipRecord() { Time = 3, Member1 = "f", Member2 = "e" },
new FrienshipRecord() { Time = 4, Member1 = "a", Member2 = "f" },
new FrienshipRecord() { Time = 5, Member1 = "c", Member2 = "a" },
};
var socialNetwork = new List<HashSet<string>>();
int totalMembersCount = 6;
foreach (var record in log)
{
var group1 = socialNetwork.FirstOrDefault(g => g.Contains(record.Member1));
var group2 = socialNetwork.FirstOrDefault(g => g.Contains(record.Member2));
switch (group1 is null, group2 is null)
{
case (false, false) when group1 == group2:
// do nothing
break;
case (false, false) when group1 != group2:
MergeGroups(socialNetwork, group1, group2);
break;
case (false, true):
group1.Add(record.Member2);
break;
case (true, false):
group2.Add(record.Member1);
break;
case (true, true):
socialNetwork.Add(new HashSet<string>() { record.Member1, record.Member2 });
break;
}
// If the social network contains only one group
// and also the grop contains all the members
if (socialNetwork.Count == 1 && socialNetwork[0].Count == totalMembersCount)
{
Console.WriteLine("All members were friends at " + record.Time);
return;
}
}
Console.WriteLine("Not all of the members are friends yet");
}
private static void MergeGroups(
List<HashSet<string>> socialNetwork,
HashSet<string> group1,
HashSet<string> group2)
{
if (group1.Count > group2.Count)
{
group1.UnionWith(group2);
socialNetwork.Remove(group2);
}
else
{
group2.UnionWith(group1);
socialNetwork.Remove(group1);
}
}
}
internal struct FrienshipRecord
{
internal int Time;
internal string Member1;
internal string Member2;
}
}
view raw List<HashSet<string>> hosted with ❤ by GitHub

Time Complexity Analysis:

HashSet.Add(newFriend) -> O(1) if Count is less than Capacity, otherwise O(k) where k is Count

HashSet.UnionWith(anotherHashSet) -> O(l) if Capacity is less than Count plus l, otherwise O(Count + l) where l is anotherHashSet.Count

HashSet.Contains(member) -> O(1)

Loop:

  1. Take a record from the log
  2. Get groups ids for each member {HashSet.Contains(member)} -> 2 * O(1)
  3. If the ids are the same then do nothing
  4. If one of the ids is null then add the member {HashSet.Add(newFriend) -> O(1) or O(k)
  5. If both are null then create new Group {new HashSet{a, b}} -> O(2)
  6. If not null and different then merge groups {HashSet.UnionWith} -> O(l)
  7. If the base List.Count is 1 and List[0].Count equals n then the current record is the answer

The total complexity is m * O(l). It is possible to minimize l by comparing HashSet.Count and anotherHashSet.Count, and then adding smallest to the biggest.

This way the total complexity is about O(m * log(n)) which makes the answer acceptable.

Posted on

LeetCode: Add Two Numbers (Solution)

Link to the description of the task: https://leetcode.com/problems/add-two-numbers/

public class ListNode
{
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null)
{
this.val = val;
this.next = next;
}
}
public class Solution
{
public ListNode AddTwoNumbers(ListNode firstListNode, ListNode secondListNode)
{
var currentNodes = (first: firstListNode, second: secondListNode);
var carry = 0;
var resultFirstNode = SumNodes(currentNodes, ref carry);
var resultLastNode = resultFirstNode;
while (TryMoveForward(ref currentNodes))
{
Extend(ref resultLastNode, SumNodes(currentNodes, ref carry));
}
if (carry > 0)
{
Extend(ref resultLastNode, new ListNode(carry));
}
return resultFirstNode;
}
private static bool HaveComeToEnd((ListNode first, ListNode second) nodes) =>
nodes.first is null && nodes.second is null;
private static void Extend(ref ListNode node, ListNode extension)
{
node.next = extension;
node = node.next;
}
private static bool TryMoveForward(ref (ListNode first, ListNode second) currentNodes)
{
currentNodes.first = currentNodes.first?.next;
currentNodes.second = currentNodes.second?.next;
return !HaveComeToEnd(currentNodes);
}
private static ListNode SumNodes((ListNode first, ListNode second) nodes, ref int carry)
{
var firstDigit = nodes.first is null ? 0 : nodes.first.val;
var secondDigit = nodes.second is null ? 0 : nodes.second.val;
var sum = SumDigits(firstDigit, secondDigit, ref carry);
return new ListNode(sum);
}
private static int SumDigits(int first, int second, ref int carry)
{
var total = first + second + carry;
var sum = total % 10;
carry = (total - sum) / 10;
return sum;
}
}
view raw LeetCodeAddTwoNumbers.cs hosted with ❤ by GitHub

Conclusion:

It looks pretty nice!