# Posts published in “Uncategorized”

Given a positive integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.

Example:

Input: 3
Output:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

## Solution: Simulation

Time complexity: O(n^2)
Space complexity: O(n^2)

## C++

Invert a binary tree.

Example:

Input:

     4
/   \
2     7
/ \   / \
1   3 6   9

Output:

     4
/   \
7     2
/ \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

## Solution: Recursion

Recursive invert the left and right subtrees and swap them.

Time complexity: O(n)
Space complexity: O(h)

## Python3

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Constraints:

• 1 <= hours.length <= 10000
• 0 <= hours[i] <= 16

## Solution: Target sum == 1

This problem can be reduced to find the longest subarray with sum of 1, or the longest subarray starting from left-most that has a sum greater than 0.

e.g. [6, 6, (6, 9, 9), 6, 6] => sum = 1
e.g. [9, 9, 9] => sum = 3

Time complexity: O(n)
Space complexity: O(n)

## 1017. Convert to Base -2

Solution: Math / Simulation

Time complexity: O(logn)
Space complexity: O(logn)

## 1018. Binary Prefix Divisible By 5

Solution: Math

Time complexity: O(n)
Space complexity: O(1)

## 1019. Next Greater Node In Linked List

Solution: Reverse + Monotonic Stack

Process in reverse order and keep a monotonically increasing stack, pop all the elements that are smaller than the current one, then the top of the stack (if exists) will be the next greater node.

Time complexity: O(n)
Space complexity: O(n)

## 1020. Number of Enclaves

Solution: DFS / Connected Components

Time complexity: O(mn)
Space complexity: O(mn)

## C++

We are given that the string "abc" is valid.

From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V.  (X or Y may be empty.)  Then, X + "abc" + Y is also valid.

If for example S = "abc", then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc".  Examples of invalid strings are: "abccba""ab""cababc""bac".

Return true if and only if the given string S is valid.

Example 1:

Input: "aabcbc"
Output: true
Explanation:
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".


Example 2:

Input: "abcabcababcc"
Output: true
Explanation:
"abcabcabc" is valid after consecutive insertings of "abc".
Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".


Example 3:

Input: "abccba"
Output: false


Example 4:

Input: "cababc"
Output: false

Note:

1. 1 <= S.length <= 20000
2. S[i] is 'a''b', or 'c'

## Solution: Stack

If current char can be appended to the stack do so, if the top of stack is “abc” pop, otherwise push the current char to the stack. Check whether the stack is empty after all chars were processed.

Time complexity: O(n)
Space complexity: O(n)

## C++

Mission News Theme by Compete Themes.