- Identify the ordered answer range or sorted search domain.
- Write a predicate whose truth changes only once.
- Move the appropriate boundary after each midpoint check and return the final feasible position.
Code notes
- 142 lines of TypeScript from the credited upstream file 2759.ts.
- The implementation visibly relies on sequence storage.
- 5 loop blocks detected.
Complexity
Multiply the logarithmic number of midpoint checks by the cost of one predicate evaluation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1type JSONValue =2 | null3 | boolean4 | number5 | string6 | JSONValue[]7 | { [key: string]: JSONValue };8 9class JSONParser {10 private str: string;11 private i: number;12 13 constructor(str: string) {14 this.str = str;15 this.i = 0;16 }17 18 public parse(): JSONValue {19 return this.parseValue();20 }21 22 private parseValue(): JSONValue {23 switch (this.str[this.i]) {24 case '{':25 return this.parseObject();26 case '[':27 return this.parseArray();28 case 't': 29 case 'f': 30 case 'n': 31 return this.parseLiteral();32 case '"':33 return this.parseString();34 default:35 return this.parseNumber();36 }37 }38 39 private parseObject(): JSONValue {40 ++this.i;41 42 const ans: JSONValue = {};43 44 while (this.i < this.str.length && this.str[this.i] !== '}') {45 const key = this.parseString();46 this.expectChar(':');47 const value = this.parseValue();48 49 ans[key] = value;50 if (this.str[this.i] === ',') {51 ++this.i;52 }53 }54 55 ++this.i;56 return ans;57 }58 59 private parseArray(): JSONValue[] {60 ++this.i;61 62 const ans: JSONValue[] = [];63 64 while (this.i < this.str.length && this.str[this.i] !== ']') {65 const value = this.parseValue();66 ans.push(value);67 if (this.str[this.i] === ',') {68 ++this.i;69 }70 }71 72 ++this.i;73 return ans;74 }75 76 private parseLiteral(): boolean | null {77 if (this.str.startsWith('true', this.i)) {78 this.i += 4;79 return true;80 }81 if (this.str.startsWith('false', this.i)) {82 this.i += 5;83 return false;84 }85 if (this.str.startsWith('null', this.i)) {86 this.i += 4;87 return null;88 }89 throw new Error(`Unexpected token at position ${this.i}`);90 }91 92 private parseString(): string {93 let ans = '';94 ++this.i;95 96 while (this.i < this.str.length && this.str[this.i] !== '"') {97 ans += this.str[this.i];98 ++this.i;99 }100 101 ++this.i;102 return ans;103 }104 105 private parseNumber(): number {106 let start = this.i;107 108 if (this.str[this.i] === '-') {109 ++this.i;110 }111 112 while (this.i < this.str.length && this.isDigit(this.str[this.i])) {113 ++this.i;114 }115 116 if (this.str[this.i] === '.') {117 ++this.i;118 while (this.i < this.str.length && this.isDigit(this.str[this.i])) {119 ++this.i;120 }121 }122 123 return Number(this.str.slice(start, this.i));124 }125 126 private isDigit(n: string): boolean {127 return n >= '0' && n <= '9';128 }129 130 private expectChar(char: string): void {131 if (this.str[this.i] !== char) {132 throw new Error(`Expected '${char}' at position ${this.i}`);133 }134 ++this.i;135 }136}137 138function jsonParse(str: string): JSONValue {139 const parser = new JSONParser(str);140 return parser.parse();141}142