How to solve ‘studentsAge’ in CodeFights

The Problem:

My friend Albi is a teacher. At the beginning of each lesson, her students form a line and enter the class one by one. As they enter, each student shakes her hand. Albi enters the students’ names in a list in the order in which they enter the classroom. After work, she analyzes the list to get a hint of the connections and relationships in the class.

Albi has a hunch that the ages of the students can tell her a lot. She has a list of the ages of her students in the order they entered the classroom, and she wants to calculate the number of pairs of students such that their age difference is exactly 1, and the youngest student in the pair entered before the oldest. Please help my friend!

Example

• For students = [2, 4, 3, 4, 6], the output should be
  studentsAge(students) = 2.

  There are two pairs of students Albi would be interested in: (2, 3) and (3, 4).

• For students = [5, 4, 9, 10], the output should be
  studentsAge(students) = 1.

  The only interesting pair of students in (9, 10).

Input/Output

• [time limit] 4000ms (py)

• [input] array.integer students

  The ages of the students in the order they entered the classroom.

  Guaranteed constraints:
  1 ≤ students.length ≤ 105,
  0 ≤ students[i] ≤ 105.

• [output] integer

  An integer with the answer for Albi.

The Solution:

def studentsAge(s):
    m=[0]*5**9
    c=0
    for x in s:
        c+=m[x-1]
        m[x]+=1
    return c

The Explanation:

There are multiple ways to solve this problem. Smarter way is to use a dictionary and store how many times each element is seen. However, to achieve the shortest solution (62 character in Python), we need a less efficient approach. Instead of a dictionary, create an array of size 10^5 and use this array to count each element.

For each element x in array, we need how many times x-1 is seen before that. So, for each element, we sum up this number and return it. The reason the array is initialized with length 5^9 is to decrease 1 character from 10^6.