Count the number of leaders in both sides (slices) of an array in C#. Codility EquiLeaders task

Question

EquiLeader

---

A non-empty array A consisting of N integers is given. The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.

For example, given array A such that:

A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2 we can find two equi leaders:

0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4. 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4. The goal is to count the number of equi leaders.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

For example, given:

A[0] = 4
A[1] = 3
A[2] = 4
A[3] = 4
A[4] = 4
A[5] = 2 the function should return 2, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000]; each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

This is the code I wrote, final score is a 100%. It took me a couple of tries (and days) like most of the solutions I'm posting here. Is it good code? What can be improved? I saw a question about SOLID a couple of hours ago, and that led me to start reading about the subject. This exercises are very specific and won't be extended, so (I know I'm not applying this principles here) should I still apply those principles to this kind of exercises (to practice and get used to them) or just leave it to real life extensible things?

using System;
using System.Collections.Generic;
class Solution {
 public int solution(int[] A) {
 Dictionary<int, int> leftPartition = new Dictionary<int, int>();
 Dictionary<int, int> rightPartition = new Dictionary<int, int>();
 int leadersCounter = 0;
 int leftPartitionSize = 1, rightPartitionSize = A.Length;
 int candidate, leader;
 for (int index = A.Length - 1; index >= 0; index--)
 {
 candidate = A[index];
 if (rightPartition.ContainsKey(candidate))
 {
 rightPartition[candidate]++;
 }
 else
 {
 rightPartition.Add(candidate, 1);
 }
 }
 leader = A[0];
 for (int index = 0; index < A.Length; index++)
 {
 candidate = A[index];
 if (leftPartition.ContainsKey(candidate))
 {
 leftPartition[candidate]++;
 }
 else
 {
 leftPartition.Add(candidate, 1);
 }
 rightPartition[candidate]--;
 rightPartitionSize--;
 if (leftPartition[candidate] > leftPartitionSize / 2)
 {
 leader = candidate;
 }
 if (leftPartition[leader] > leftPartitionSize / 2 && rightPartition[leader] > rightPartitionSize / 2 )
 {
 leadersCounter++;
 }
 leftPartitionSize++;
 }
 return leadersCounter;
 }
}

Answer 1

• If you need to get a value of a Dictionary<TKey, TValue> you shouldn't us ContainsKey() together with the Item property getter but TryGetValue(), because by using ContainsKey() in combination with the Item getter you are doing the check if the key exists twice.
  From the refernce source

  public bool ContainsKey(TKey key)
  {
   if (key == null) throw new ArgumentNullException("key");
   TValue throwAwayValue;
   return TryGetValue(key, out throwAwayValue);
  }
  public TValue this[TKey key]
  {
   get
   {
   TValue value;
   if (!TryGetValue(key, out value))
   {
   throw new KeyNotFoundException();
   }
   return value;
   }
   set
   {
   if (key == null) throw new ArgumentNullException("key");
   TValue dummy;
   TryAddInternal(key, value, true, true, out dummy);
   }
  }
  

• Multiple declarations of variables on a single line should be avoided because it reduces the readability of the code.

• If the type is clear from the right-hand-side of an assignment one should use var instead of the concrete type.

• You should declare the variables as near to their usage as possible. This makes reading the code easier as well.

• Althought this is from a programming excercise please note that methods should be named using PascalCase casing and method parameters should be named using camelCasecasing. Meaning solution should be Solution and A should be a if we talk about casing.

Implementing the mentioned points (without casing stuff) will look like this

public int solution(int[] A)
{
 var leftPartition = new Dictionary<int, int>();
 var rightPartition = new Dictionary<int, int>();
 for (var index = A.Length - 1; index >= 0; index--)
 {
 var candidate = A[index];
 rightPartition.TryGetValue(candidate, out int value);
 rightPartition[candidate] = value + 1;
 }
 var leadersCounter = 0;
 var leftPartitionSize = 1;
 var rightPartitionSize = A.Length;
 var leader = A[0];
 for (var index = 0; index < A.Length; index++)
 {
 var candidate = A[index];
 leftPartition.TryGetValue(candidate, out int value);
 leftPartition[candidate] = value + 1;
 rightPartition[candidate]--;
 rightPartitionSize--;
 if (leftPartition[candidate] > leftPartitionSize / 2)
 {
 leader = candidate;
 }
 if (leftPartition[leader] > leftPartitionSize / 2 && rightPartition[leader] > rightPartitionSize / 2)
 {
 leadersCounter++;
 }
 leftPartitionSize++;
 }
 return leadersCounter;
}