Valid Elements in a sorted array

Problem: Statement Write a function to count number of distinct elements given in a sorted array.

Difficulty level: Easy

Test Cases

• [2, 2, 3, 3, 4, 5] --> 4
• [4, 5, 7, 10, 15] --> 5
• [1, 1, 1, 2, 5, 5, 5] --> 3
• [1, 2, 3, 4, 4, 5, 5, 5] --> 5
• None --> 0

Algorithm

• Python Set Solution

  • Add elements of array to set and return it's length.

• Dictionary Solution

  • Iterate through the given array
  • If element was previously not seen in dictionary than,
  • Add the element to dictionary with value of 1.
  • Return the length of dictionary.

• Best Solution

  • Initialise index at 1
  • Iterate from 1 to length of given array.
  • If, the element at current iteration i is not equal to element at position of index - 1, than
  • Overwrite the element at index with the element at current iteration i
  • increment value of index by 1
  • Return index

Time and Space complexity

• Time complexity of all solutions: O(n)

• Space complexity

  • Set: O(n)
  • Dictionary: O(n)
  • Best solution: O(1)

Code

class ValidElements(object): def validElements(self, arr): if not arr: return 0 return len(set(arr)) def validElements2(self, arr): if not arr: return 0 seen = {} for entry in arr: if entry not in seen: seen[entry] = 1 return len(seen) def validElements3(self, arr): if not arr: return 0 index = 1 for i in range(1, len(arr)): if arr[index - 1] != arr[i]: arr[index] = arr[i] index += 1 print(arr) return index 

Unit Test

import unittest from validElements import ValidElements class TestValidElements(unittest.TestCase): def testValidElements(self, func): self.assertEqual(func([2, 2, 3, 3, 4, 5]), 4) self.assertEqual(func([1, 2, 3, 4, 4, 5, 5, 5]), 5) self.assertEqual(func([1, 1, 1, 2, 5, 5, 5]), 3) print("All test cases passed") def main(): test = TestValidElements() elements = ValidElements() test.testValidElements(elements.validElements) test.testValidElements(elements.validElements2) test.testValidElements(elements.validElements3) if __name__ == "__main__": main() 

Original article
Github solution

Happy Coding ! 😃