[Hackerrank] Grid Challenge

Problem

Given a squared sized grid G of size N in which each cell has a lowercase letter. Denote the character in the ith row and in the jth column as G[i][j].
You can perform one operation as many times as you like: Swap two column adjacent characters in the same row G[i][j] and G[i][j+1] for all valid i,j.
Is it possible to rearrange the grid such that the following condition is true?
G[i][1]G[i][2]G[i][N] for 1iN and 
G[1][j]G[2][j]G[N][j] for 1jN
In other words, is it possible to rearrange the grid such that every row and every column is lexicographically sorted?
Notec1c2, if letter c1 is equal to c2 or is before c2 in the alphabet.
Input Format
The first line begins with T, the number of testcases. In each testcase you will be given N. The following N lines contain N lowercase english alphabet each, describing the grid.
Output Format
Print T lines. On the ith line print YES if it is possible to rearrange the grid in the ith testcase or NO otherwise.
Constraints 
1T100 
1N100 
Gij will be a lower case letter
Sample Input
1
5
ebacd
fghij
olmkn
trpqs
xywuv
Sample Output
YES

Analysis

  • Sort each row
  • Then check each column to check whether numbers are in increasing order or not

Code

[Hackerrank] Sherlock and Array

Problem

Watson gives Sherlock an array A of length N. Then he asks him to determine if there exists an element in the array such that the sum of the elements on its left is equal to the sum of the elements on its right. If there are no elements to the left/right, then the sum is considered to be zero.
Formally, find an i, such that, A1+A2...Ai-1 =Ai+1+Ai+2...AN.
Input Format
The first line contains T, the number of test cases. For each test case, the first line contains N, the number of elements in the array A. The second line for each test case contains Nspace-separated integers, denoting the array A.
Output Format
For each test case print YES if there exists an element in the array, such that the sum of the elements on its left is equal to the sum of the elements on its right; otherwise print NO.
Constraints
1T10
1N105
1Ai 2×104
1iN
Sample Input
2
3
1 2 3
4
1 2 3 3
Sample Output
NO
YES
Explanation
For the first test case, no such index exists.
For the second test case, A[1]+A[2]=A[4], therefore index 3 satisfies the given conditions.

Analysis

  • First calculate the sum of all elements
  • Maintain curr as the cumulated sum in the left parts, when traversing the array
    • if (curr == sum – curr – arr[i]), then it means the sum in the left part and right part of arr[i] equals
  • Time: 
    • O(n), as the array has been traversed twice
  • Space
    • O(1)

Code

[Hackerrank] Time Conversion

Problem

Given a time in AM/PM format, convert it to military (24-hour) time.
Note: Midnight is 12:00:00AM on a 12-hour clock and 00:00:00 on a 24-hour clock. Noon is 12:00:00PM on a 12-hour clock and 12:00:00 on a 24-hour clock.
Input Format
A time in 12-hour clock format (i.e.: hh:mm:ssAM or hh:mm:ssPM), where 01hh12.
Output Format
Convert and print the given time in 24-hour format, where 00hh23.
Sample Input
07:05:45PM
Sample Output
19:05:45
Explanation
7 PM is after noon, so you need to add 12 hours to it during conversion. 12 + 7 = 19. Minutes and seconds do not change in 12-24 hour time conversions, so the answer is 19:05:45.

Analysis

  • 首先截取后两位字母,判断是AM还是PM
  • 注意关于时间,只需要改hour
    • 取hour
    • 如果PM
      • 若hour<12, 则加12,否则不变
      • 如 12:xx:xxPM, should be 12:xx:xx
      • 11:xx:xxPM should be 23:xx:xx
    • 如果AM
      • 若hour>12, 则转为0
      • 否则不变

Code