Question

Yesterday you found some shoes in the back of your closet. Each shoe is described by two values:

• type indicates if it's a left or a right shoe;
• size is the size of the shoe.

Your task is to check whether it is possible to pair the shoes you found in such a way that each pair consists of a right and a left shoe of an equal size.

Example

• For

  shoes = [[0, 21], 
           [1, 23], 
           [1, 21], 
           [0, 23]]
  

  the output should be
  pairOfShoes(shoes) = true;

• For

  shoes = [[0, 21], 
           [1, 23], 
           [1, 21], 
           [1, 23]]
  

  the output should be
  pairOfShoes(shoes) = false.

Input/Output

• [execution time limit] 4 seconds (py3)

• [input] array.array.integer shoes

  Array of shoes. Each shoe is given in the format [type, size], where type is either 0 or 1 for left and right respectively, and size is a positive integer.

  Guaranteed constraints:
  1 ≤ shoes.length ≤ 200,
  1 ≤ shoes[i][1] ≤ 100.

• [output] boolean

  true if it is possible to pair the shoes, false otherwise.

Input:

shoes: [[0,21], [1,23], [1,21], [0,23]]

Expected Output:

true

shoes: [[0,21], [1,23], [1,21], [1,23]]

Expected Output:

false

Use Python

def pairOfShoes(shoes):

Answer 1

The answer to the above problem is as follows:

• first the function will be defined.
• Then inside the function, define an empty array of 100 rows and 2 columns, each array will act as a hash table that stores the shoes data, each row index of hash table means the shoe size, and if column 0 has value 1, it means left shoe is there for this size and if column 1 has value 1, it means right shoe is there for this size.
• the hash table is created and then further operations are carried out as mentioned in the comments of the code.

PYTHON CODE-

#define the method that takes the shoes array as input parameters
def pairOfShoes(shoes):
#define an empty array of 100 rows and 2 columns,
#each array will act as a hash table that stores the shoes data
#each row index of hash table means the shoe size
#and if column 0 has value 1, it means left shoe is there for this size
#and if column 1 has value 1, it means right shoe is there for this size
  
#create a hash table to store the data of shoes in a way define above
#row size is 101, because we have shoe size from 1 to 100, and arrays are 0 indexed
a = [[0 for x in range(2)] for y in range(101)]
  
#iterate over the shoes array
for i in range(len(shoes)):
#for left shoe, have value 1 in column 0 in the hash table for that shoe
if(shoes[i][0] == 0):
a[shoes[i][1]][0] = 1
#for right shoe, have value 1 in column 1 in the hash table for that shoe
elif(shoes[i][0] == 1):
a[shoes[i][1]][1] = 1
  
#initially flag is True
flag = True
  
#iterate over the hash table array
for i in range(1,len(a)):
#if at that row, there is atleast 1 column with value 1, it means there is one shoe that might be left or right
if(a[i][0]==1 or a[i][1]==1):
#check if both left and right are not there, meaning either column 0 or 1 has the value which is not 1
if(a[i][0]!=1 or a[i][1]!=1):
#it means the pair is not there
flag = False #set flag False
break #break the loop
  
#return the result
return flag
  
#demo values and function call to test the function and display the result
shoes = [[0,21], [1,23], [1,21], [0,23],[0,18],[1,19]]
print(pairOfShoes(shoes))

IMAGE OF CODE and OUTPUT-

If this answer helps, please give an up vote and feel free to comment for any query.